Алгоритм Монтгомери

Алгоритм Монтгомери, приём, позволяющий ускорить выполнение операций умножения и возведения в квадрат, необходимых при возведение числа в степень по модулю, когда модуль велик (порядка сотен бит). Был предложен в 1985 году Питером Монтгомери.

По данным целым числам a, b < n, r, НОД(r,n) = 1 А.М. вычисляет

Положим r = 2k.

Определим n-остаток (n-residue) числа a < n как .

А.М. использует свойство, что множество  является полной системой вычетов, то есть содержит все числа от 0 до n-1.

MonPro вычисляет . Результат является n-остатком от , так как

Определим n' так, что . r − 1 и n' можно вычислить с помощью расширенного алгоритма Евклида.

Функция 

1.

2.

3. if(u<0)while (u < 0)u = u + n

4. return

Операции умножения и деления на r выполняются очень быстро, так как при r = 2k представляют собой просто сдвиги бит. Таким образом А.М. быстрее обычного вычисления, которое содержит деление на n. Однако вычисление n' и перевод чисел в n-остатки и обратно — трудоёмкие операции, вследствие чего применять А.М. при вычислении произведения двух чисел представляется неразумным.

Использование А.М. оправдывает себя при возведении числа в степень по модулю .

Функция ModExp(a,e,n)

1.

2.

3. for i=j-1 downto 0

if ei = 1 then

4. return

Возведение числа в степень битовой длины k алгоритмом «возводи в квадрат и перемножай» включает в себя от k до 2k умножений, где k имеет порядок сотен или тысяч бит. При использовании алгоритма возведения в степень Монтгомери объём дополнительных вычислений фиксирован (вычисления n', ,  в начале и  в конце), а операция MonPro выполняется быстрее обычного умножения по модулю, поэтому алгоритм возведения в степень Монтгомери даст выигрыш в производительности по сравнению с алгоритмом «возводи в квадрат и перемножай».