Теория и практика защиты программ


Алгоритм 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-той итерации (т.е.


- Начало -  - Назад -  - Вперед -