Алгоритм A*B modulo N алгоритм выполнения + операции модулярного умножения
Алгоритм A*B modulo N алгоритм выполнения + операции модулярного умножения
Операнды многократной точности для данного алгоритма представляются в виде одномерного массива целых чисел. Для знака можно зарезервировать элемент с нулевым индексом. Особенности представления чисел при организации взаимодействия алгоритма с другими рабочими программами, при организации вводавывода и т.д. рассматриваются, например, в работе. В алгоритме использован известный вычислительный метод "разделяй и властвуй" и реализован способ вычисления "цифразацифрой". Прямое умножение не следует делать по нескольким причинам: вопервых, произведение A*B требует в два раза больше памяти, чем при методе "цифразацифрой"; вовторых, умножение двух многоразрядных чисел труднее организовать, чем умножение числа многократной точности на число однократной точности. Так, в работе приводятся расчеты на суперЭВМ "CRAY2" для 100разрядных десятичных чисел: модулярное умножение методом "цифразацифрой" выполняется примерно на 10% быстрее, чем прямое умножение и следующая за ним модульная редукция.
Так как B[i] [0,...,2 λ/21], то проверку "if B[i]<>0" в алгоритме P можно не вводить потому, что вероятность того, что B[i] будет равняться 0 пренебрежимо мала, если значение λ не достаточно малым. Ошибка затем все равно будет алгоритмом обнаружена. Проверка
"if p_shortk*n_short>n_short DIV 2"
позволяет представлять k числом однократной точности и работать с наименьшими абсолютными остатками в каждой итерации. Значение операнда Pi на каждом шаге итерации должно быть ограничено величиной N.
Теорема 2.1. Пусть Pi частичное произведение P в конце iтой итерации (т.е. в конце iтого цикла FOR алгоритма P). Тогда для любого i (i=[1,...,n]) abs(Pi)<N, rm1 N rm.
Доказательство теоремы 2.1. Доказательство теоремы проведем методом индукции. Если k=abs(p_short) DIV n_short, где DIV целочисленное деление, то
p_short=(k+δ)*n_short, (2.1.6)
где k целое, 0 k < r1 и 0 δ < 1.
Проверка "if p_shortk*n_short>n_short DIV 2" есть ни что иное, как проверка
δ > 0.5 (2.1.7)
На iтом шаге алгоритм вычисляет:
P'=Pi1*r+A*B[i] (2.1.8)
Возможны два варианта:
Вариант 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'
Pi= δ*N, если δ 0.5 (2.1.11)
и так как Pi=P'+(k+1)*N, то
Pi=(1δ)*N, если δ > 0.5 (2.1.12)
Алгоритм 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_shortk*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 результат}
Алгоритм 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 результат}
(процедура ADDK)
Вариант B:
p_short>0 (2.1.13)
Из (2.1.9) и (2.1.13) следует P'>N и так как Pi=P'k*N, то согласно (2.1.7)
Pi=δ *N, если δ 0.5 (2.1.14)
и так как Pi=P'(k+1)*N, то
Pi=(1δ)*N, если δ > 0.5 (2.1.15)
Во всех случаях (2.1.11), (2.1.12), (2.1.14) и (2.1.15), так как 0 δ < 1, то abs(Pi) < N. Теорема доказана
.Примечание. Для чего нужна проверка (2.1.7)
"if p_shortk*n_short>n_short DIV 2" ?
Пусть в конце каждой итерации P принимает максимально возможное значение Pi1=N1, а N, A и B[i] заведомо тоже велики: N=rn+11, A=rn+12, B[i]=r1. Тогда на iтом шаге согласно (2.1.8):
Pi'=(rn+12)*r+(rn+12)*(r1)=2*rn+2rn+14*r+2(2.1.16)
(2.1.17)
При достаточно большом m, если не введена проверка (2.1.6), то k < 2*r1, по условию же 0< k < r 1. И из (2.1.16) и (2.1.17) видно, что P придется представлять m+2 разрядами (что определяется слагаемым 2*rn+2), по условию же m+1. Если же ввести проверку (2.1.7), то даже при δ=0,5 т.е.
Pi1=(N1)/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)*r1, что удовлетворяет наложенному на k условию, и для представление P достаточно m+1 разряда.
В алгоритме P используется также известный метод, когда для получения частного от деления двух многоразрядных чисел, используются только старшие цифры этих чисел (см., например, алгоритм D в работе [36, стр.291295]). Чем больше основание системы счислени r, тем ниже вероятность того, что пробное частное k от деления первых цифр больших чисел не будет соответствовать действительному частному.
Методы доказательства правильности программ могут быть применены для анализа безопасности ПО при существенных ограничениях на размеры и сложность создаваемых программ. Поэтому в частных случаях они могут оказаться более эффективными, чем другие известные методы анализа программ, которые исследуются в следующих разделах данной работы.
4/04/10 - 
