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

Алгоритм Монтгомери — приём, позволяющий ускорить выполнение операций умножения и возведения в квадрат, необходимых при возведении числа в степень по модулю, когда модуль велик (порядка сотен бит). Был предложен в 1985 году Питером Монтгомери.
 По данным целым числам a, b \textless n, r, НОД(r,n)=1 алгоритм Монтгомери вычисляет
MonPro(a,b)=abr1modn

Умножение Монтгомери


 Положим r=2k.
 Определим n-остаток (n-residue) числа a<n как a¯=armodn.
 Алгоритм Монтгомери использует свойство, что множество {armodn0an1} является полной системой вычетов, то есть содержит все числа от 0 до n-1.
 MonPro вычисляет c¯=a¯b¯r1modn. Результат является n-остатком от c=abmodn, так как
c¯=a¯b¯r1modn=arbrr1modn=crmodn
 Определим n' так, что rr1nn=1. r1 и n можно вычислить с помощью расширенного алгоритма Евклида.
 Функция MonPro(a¯,b¯)
 \texttt1. t=a¯b¯\\\texttt2. u=(t+(tnmodr)n)/r\\\texttt3. '''while '''(u<0)u=u+n\\\texttt4. '''return ''' umodn
 Операции умножения и деления на r выполняются очень быстро, так как при r=2k представляют собой просто сдвиги бит. Таким образом алгоритм Монтгомери быстрее обычного вычисления abmodn, которое содержит деление на n. Однако вычисление n' и перевод чисел в n-остатки и обратно — трудоёмкие операции, вследствие чего применять алгоритм Монтгомери при однократном вычислении произведения двух чисел представляется неразумным.

Возведение в степень Монтгомери


 Использование алгоритма Монтгомери оправдывает себя при возведении числа в степень по модулю aemodn.
 Функция ModExp(a,e,n)
 \texttt1. a¯=armodn\\\texttt2. x¯=1rmodn\\\texttt3. for i=j-1 downto 0\\\texttt     x¯=MonPro(x¯,x¯)\\\texttt     if ei=1\texttt then x¯=MonPro(x¯,a¯)\\\texttt4. return x=MonPro(x¯,1)
 Возведение числа в степень битовой длины k алгоритмом «возводи в квадрат и перемножай» включает в себя от k до 2k умножений, где k имеет порядок сотен или тысяч бит. При использовании алгоритма возведения в степень Монтгомери объём дополнительных вычислений фиксирован (вычисления n, a¯, x¯ в начале и MonPro(x¯,1) в конце), а операция MonPro выполняется быстрее обычного умножения по модулю, поэтому алгоритм возведения в степень Монтгомери даст выигрыш в производительности по сравнению с алгоритмом «возводи в квадрат и перемножай».