Модулярное умножение длинных чисел

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

D:=A Ч B;

С := D mod P.

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

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

D := А²;

С := D mod P.

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

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

КоL=(mod Р), где Е = bⁿ (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 = -P₀^-1(mod b)

1. S:=0;

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

3. S:=S + K Ч L_i;

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

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

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

7. конец.

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

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

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

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

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

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


Операцию умножения по модулю можно выполнять следующим образом. Если А и В < Р, то С = (А Ч В) (mod P) вычисляется так: D:=A Ч B; С := D mod P. Аналогичным образом выполняется вычисление квадрата по модулю, С = A² (mod P) вычисляется так: D := А²; С := D mod P. Операция Монтгомери Однако действовать таким образом ввиду усложненной операции деления неэффективно, поэтому предлагается слегка модифицировать операцию умножения на множестве чисел {0,1…Р-1}. Определим новую операцию умножения следующим образом: КоL=(mod Р), где Е = bⁿ (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 = -P₀^-1(mod b) 1. S:=0; 2. для i = 0…n-l выполнить 3-5; 3. S:=S + K Ч L_i; 4. e:=S₀Ч z(mod b); 5. S:=(S + e Ч P)/b; 6. если S >= P, то S := S — P; 7. конец. Следует заметить, что результат сложения S на шаге 5 может иметь значение длины n+1 цифра.Число z можно было бы, конечно вычислить на первом шаге алгоритма, но поскольку оно зависит только от модуля Р, а он не изменяется при выполнении, скажем, алгоритма возведения в степень, то удобно заранее подготовить этот параметр. Как видно из алгоритма, выигрыш состоит в том, что на каждом шаге выполняется умножение для вычисления очередного значения е, а не деление, как это было в алгоритме деления. Кроме того, деления на b выполнять не надо: оно равносильно смещению индекса частного, которая то и дело возникала при делении. В общем, при той же теоретической сложности порядка n² операция Монтгомери практически выполняется быстрее обычного модулярного у. Дальнейшие уточнения этого алгоритма связаны с оптимизацией внутренних циклов (умножения К * L_i и е * Р). В частности, возможно объединение двух этих циклов в один.Если вычисления выполняются на многопроцессорной платформе, можно выполнять эти операции на двух процессорах параллельно со сдвигом на 1 такт. Имеется симпатичное ускорение данного алгоритма для сигнальных процессоров семейства TMS, которое состоит в том, что сразу вычисляется значение очередной цифры результата с помощью алгоритма свертки (а именно свертки оптимально вычисляют сигнальные процессоры). С возведением во вторую степень поступим просто. Будем вычислять S = K² ( в смысле умножения Монтгомери) по определению S = КоК (mod P). Можно воспользоваться возведением в квадрат по алгоритму «треугольника» для ускорения этой операции. Выигрыш может составить до 10-15% и более. Для корректного использования операции Монтгомери при выполнении модулярного возведения в степень необходимы функции, реализующие изоморфизмы f и f^-1. И, наконец, последнее, что необходимо определить для того, чтобы использовать алгоритм Монтгомери, это нахождение параметра z. Так получилось, что итоге придется решать задачу нахождения мультипликативного обратного для произвольного числа по модулю Р.
Просмотров: 422 \| Добавлено: 10.03.2015, 04:12