Алгоритм 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=P'+k*N, то согласно (2.1.7)

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 от деления первых цифр больших чисел не будет соответствовать действительному частному.

Методы доказательства правильности программ могут быть применены для анализа безопасности ПО при существенных ограничениях на размеры и сложность создаваемых программ. Поэтому в частных случаях они могут оказаться более эффективными, чем другие известные методы анализа программ, которые исследуются в следующих разделах данной работы.


Ведете ли вы блог?

Да
Нет
Планирую


Результаты опроса

Новостной блок