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

Алгоритм Монтгомери — приём, позволяющий ускорить выполнениеопераций умножения и возведения в квадрат, необходимых при возведениичисла в степень по модулю, когда модуль велик (порядка сотен бит). Былпредложен в 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 выполняется быстрее обычного умножения по модулю, поэтомуалгоритм возведения в степень Монтгомери даст выигрыш впроизводительности по сравнению с алгоритмом «возводи в квадрат иперемножай».