Операцию умножения по модулю можно выполнять следующим образом. Если А и В < Р, то С = (А Ч В) (mod P) вычисляется так:

D:=A Ч B;

С := D mod P.

Аналогичным образом выполняется вычисление квадрата по модулю,

С = A2 (mod P) вычисляется так:

D := А2;

С := D mod P.

Операция Монтгомери

Однако действовать таким образом ввиду усложненной операции деления неэффективно, поэтому предлагается слегка модифицировать операцию умно­жения на множестве чисел {0,1…Р-1}. Определим новую операцию умноже­ния следующим образом:

КоL=(mod Р), где Е = bn (mod P).

Желающие могут убедиться, что множество целых чисел {0,…,Р-1} с опе­рациями «+» и «о» является полем с единицей Е. Обозначим его MF(P). Это поле изоморфно полю GF(P).

Изоморфизм

f: GF(P) a MF(P)

задается формулой:

f(K) = К Ч Е (mod P).

Обратное отображение     f’: MF(P) a GF(P)

f’(S) = S о 1.

Для операции Монтгомери существует оптимизированный алгоритм, не требующий деления в поле GF(P), которое бы существенно замедлило вычис­ления. Ниже приведен этот алгоритм.

Алгоритм 1.10. Вычисление произведения Монтгомери S = KoL (mod Р); при этом z = -P0-1(mod b)

1.   S:=0;

2.   для i = 0…n-l выполнить 3-5;

3.   S:=S + K Ч Li;

4.   e:=S0 Ч z(mod b);

5.   S:=(S + e Ч P)/b;

6.   если S >= P, то S := S — P;

7.   конец.

Следует заметить, что результат сложения S на шаге 5 может иметь значе­ние длины n+1 цифра.Число z можно было бы, конечно вычислить на первом шаге алгоритма, но поскольку оно зависит только от модуля Р, а он не изменяется при выполнении, скажем, алгоритма возведения в степень, то удобно заранее подготовить этот параметр. Как видно из алгоритма, выигрыш состоит в том, что на каждом шаге вы­полняется умножение для вычисления очередного значения е, а не деление, как это было в алгоритме деления. Кроме того, деления на b выполнять не надо: оно равносильно смещению индекса частного, которая то и дело возникала при делении. В общем, при той же теоретической сложности порядка n2 операция Монтгомери практически выполняется быстрее обычного модулярного у.

Дальнейшие уточнения этого алгоритма связаны с оптимизацией внутрен­них циклов (умножения К * Li и е * Р). В частности, возможно объединение двух этих циклов в один.Если вычисления выполняются на многопроцессорной платформе, можно выполнять эти операции на двух процессорах параллельно со сдвигом на 1 такт. Имеется симпатичное ускорение данного алгоритма для сигнальных про­цессоров семейства TMS, которое состоит в том, что сразу вычисляется значе­ние очередной цифры результата с помощью алгоритма свертки (а именно свер­тки оптимально вычисляют сигнальные процессоры). С возведением во вторую степень поступим просто. Будем вычислять

S = K2 ( в смысле умножения Монтгомери) по определению S = КоК (mod P).

Можно воспользоваться возведением в квадрат по алгоритму «треугольника» для ускорения этой опера­ции. Выигрыш может составить до 10-15% и более.

Для корректного использования операции Монтгомери при выполнении модулярного возведения в степень необходимы функции, реализующие изо­морфизмы f и f-1.

И, наконец, последнее, что необходимо определить для того, чтобы исполь­зовать алгоритм Монтгомери, это нахождение пара­метра z. Так получилось, что итоге придется решать задачу нахождения мультипликативного обратного для произвольного числа по модулю Р.