Алгоритм A*B modulo N - алгоритм выполнения операции модулярного умножения
Операнды многократной точности для данного алгоритма представляются в виде одномерного массива целых чисел. Для знака можно зарезервировать элемент с нулевым индексом. Особенности представления чисел при организации взаимодействия алгоритма с другими рабочими программами, при организации ввода-вывода и т.д. рассматриваются, например, в работе [Hu]. В алгоритме использован известный вычислительный метод «разделяй и властвуй» и реализован способ вычисления «цифра-за-цифрой». Прямое умножение не следует делать по нескольким причинам: во-первых, произведение A*B
требует в два раза больше памяти, чем при методе «цифра-за-цифрой»; во-вторых, умножение двух многоразрядных чисел труднее организовать, чем умножение числа многократной точности на число однократной точности. Так, в работе [BW] приводятся расчеты на супер-ЭВМ «CRAY-2» для 100-разрядных десятичных чисел: модулярное умножение методом «цифра-за-цифрой» выполняется примерно на 10% быстрее, чем прямое умножение и следующая за ним модульная редукция. Алгоритм модулярного умножения (алгоритм P) приведен на рис.2.2, а на рис.2.1 представлен псевдокод процедуры ADDK.
Алгоритм ADDK
carry:=0;
for i:=1 to m do
begin
t:=P[i]+k*N[i]+carry;
P[i]:=t
mod r;
carry:=t div r;
end;
P[m+1]:=carry;
write(P); {P - результат}
Рис.2.1. Псевдокод алгоритма вычисления P+k*N
(процедура ADDK)
Так как B[i]Î[0,...,2l/2-1], то проверку «if B[i]<>0» в алгоритме P можно не вводить потому, что вероятность того, что B[i] будет равняться 0 пренебрежимо мала, если значение l
не достаточно мало. Ошибка затем все равно будет алгоритмом обнаружена. Проверка
«if p_short-k*n_short>n_short DIV 2»
позволяет представлять k числом однократной точности и работать с наименьшими абсолютными остатками в каждой итерации. Значение операнда Pi на каждом шаге итерации должно быть ограничено величиной N.
Теорема 2.1.
Пусть Pi - частичное произведение P в конце i-той итерации (т.е.
в конце i-того цикла FOR алгоритма P). Тогда для любого i (i=[1,...,n]) abs(Pi)<N, rm-1£N£rm.
Доказательство.
Доказательство теоремы проведем методом индукции.
Если k=abs(p_short) DIV n_short, где DIV - целочисленное деление, то
p_short=(k+d)*n_short, (2.1.6)
где k - целое, 0£k<r-1 и 0£d<1.
Проверка «if p_short-k*n_short> n_short DIV 2» есть ни что иное, как проверка
d>0.5 (2.1.7)
На i-том шаге алгоритм вычисляет:
P'=Pi-1*r+A*B[i] (2.1.8)
Алгоритм P
m_shifts:=0;
while n[m_shifts]=0 do
begin
shift_left(N and A);
m_shifts:=m_shifts+1;
end;
m:=m_shifts;
reset(P);
n_short:=N[m];
for i:=n downto 1 do
begin
shift_left(P); {сдвиг на 1 элемент влево или умножение P*r}
if b<>0 then
addk(A*B[i],{to}P);
let p_short represent the 2 high assimilated digits of P;
k:=abs(p_short) div n_short;
if p_short-k*n_short>n_short div 2 then k:=k+1;
if k>0 then
begin
if p_short<0 then
addk(k*N,{to} P)
else
addk(-k*N,{to} P);
end;
end;{for}
right shift P, N by m_shifts;
if P<0 then
P:=P+N;
write(P); {P - результат}
Рис. 2.2. Псевдокод алгоритма модулярного умножения A*B modulo N
Возможны два варианта:
Вариант 1. Если k=0, т.е. n_short>abs(p_short) (см. алгоритм), то суммирование при помощи процедуры ADDK не производится и утверждение теоремы выполняется, т.е.
abs(Pi)<N.
Вариант 2. Если k>0, т.е.
n_short<abs(p_short) (2.1.9)
Здесь также возможны два варианта:
Вариант A:
p_short<0 (2.1.10)
Из (2.1.9) и (2.1.10) следует P'<-N и так как Pi=-P'+k*N
(см. алгоритм), то согласно (2.1.7)
Pi=d*N, если d£0.5 (2.1.11)
и так как Pi=-P'+(k+1)*N, то
Pi=-(1-d)*N, если d>0.5 (2.1.12)
Вариант B:
p_short>0 (2.1.13)
Из (2.1.9) и (2.1.13) следует P'>N и так как Pi=P'-k*N, то согласно (2.1.7)
Pi=-d*N, если d£0.5 (2.1.14)
и так как Pi=P'-(k+1)*N, то
Pi=(1-d)*N, если d>0.5 (2.1.15)
Во всех случаях (2.1.11), (2.1.12), (2.1.14) и (2.1.15), так как 0£d<1, то abs(Pi)<N.
Теорема доказана n.
Примечание. Для чего нужна проверка (2.1.7)
«if p_short-k*n_short>n_short DIV 2» ?
Пусть в конце каждой итерации P
принимает максимально возможное значение Pi-1=N-1, а N, A и B[i] заведомо тоже велики: N=rn+1-1, A=rn+1-2, B[i]=r-1. Тогда на i-том шаге согласно (2.1.8):
Pi'=(rn+1-2)*r+(rn+1-2)*(r-1)=2*rn+2-rn+1-4*r+2 (2.1.16)
При достаточно большом m, если не введена проверка (2.1.6), то k<2*r-1, по условию же 0<k<r-1. И из (2.1.16) и (2.1.17) видно, что P
придется представлять m+2 разрядами (что определяется слагаемым 2*rn+2), по условию же m+1. Если же ввести проверку (2.1.7), то даже при d=0,5 т.е.
Pi-1=(N-1)/2 и с учетом того, что если неравенство (2.1.7) выполняется, то Pi
меняет знак на противоположный (сравн. (2.1.11), (2.1.12), (2.1.14) и (2.1.15)), из (2.1.6) и (2.1.7) получим, что 0£k<(1/2)*r-1, что удовлетворяет наложенному на k
условию, и для представление P
достаточно m+1 разряда.
В алгоритме P
используется также известный метод, когда для получения частного от деления двух многоразрядных чисел, используются только старшие цифры этих чисел (см., например, алгоритм D
в работе [Кн, стр.291-295]). Чем больше основание системы счисления r, тем меньше вероятность того, что пробное частное k от деления первых цифр больших чисел не будет соответствовать действительному частному.
Методы доказательства правильности программ могут быть применены при разработке ПО при существенных ограничениях на размеры и сложность создаваемых программ. И в частных случаях они могут оказаться более эффективными, чем другие известные методы анализа программ, которые исследуются в следующих разделах данной работы.
|
www.kiev-security.org.ua BEST rus DOC FOR FULL SECURITY |
