Операцию умножения по модулю можно выполнять следующим образом. Если А и В < Р, то С = (А Ч В) (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. Так получилось, что итоге придется решать задачу нахождения мультипликативного обратного для произвольного числа по модулю Р.