Русская Википедия:Алгоритм Монтгомери
Алгоритм Монтгомери — приём, позволяющий ускорить выполнение операций умножения и возведения в квадрат, необходимых при возведении числа в степень по модулю, когда модуль велик (порядка сотен бит). Был предложен в 1985 году Питером Монтгомери.
По данным целым числам a, b < n, r, НОД<math>(r,n)=1</math> алгоритм Монтгомери вычисляет
<math>MonPro(a,b) = a \cdot b \cdot r^{-1} \mod{n}</math>
В приложениях обычно берётся <math>r=2^k</math>, так как в этом случае деление с остатком и умножение на <math>r</math>, используемые внутри алгоритма, происходят быстро.
Умножение Монтгомери
Определим n-остаток (n-residue) числа <math>a < n</math> как <math>\bar{a} = a \cdot r \mod{n}</math>.
Алгоритм Монтгомери использует свойство, что множество <math>\{ a \cdot r \mod{n} \mid 0 \leqslant a \leqslant n-1 \}</math> является полной системой вычетов, то есть содержит все числа от 0 до n-1.
MonPro вычисляет <math>\bar{c} = \bar{a} \cdot \bar{b} \cdot r^{-1} \mod{n}</math>. Результат является n-остатком от <math>c = a \cdot b \mod{n}</math>, так как
<math>\bar{c} = \bar{a} \cdot \bar{b} \cdot r^{-1} \mod{n} = a \cdot r \cdot b \cdot r \cdot r^{-1} \mod{n} = c \cdot r \mod{n}</math>
Определим n' так, что <math>r \cdot r^{-1} - n \cdot n' = 1</math>. <math>r^{-1}</math> и <math>n'</math> можно вычислить с помощью расширенного алгоритма Евклида.
Функция <math>MonPro(\bar{a},\bar{b})</math>
1. <math>t = \bar{a} \cdot \bar{b}</math>
2. <math>u = (t + (t \cdot n' \mod{r} ) \cdot n ) / r</math>
3. while <math>(u >= n) u = u - n</math>
4. return <math>u</math>
При <math>r=2^{k}</math> операции умножения и деления на <math>r</math> выполняются очень быстро, так как представляют собой просто сдвиги бит, а при <math>r > n</math> цикл в строчке 3 выполнится не более одного раза. Таким образом алгоритм Монтгомери быстрее обычного вычисления <math>a \cdot b \mod{n}</math>, которое содержит деление на n. Однако вычисление n' и перевод чисел в n-остатки и обратно — трудоёмкие операции, вследствие чего применять алгоритм Монтгомери при однократном вычислении произведения двух чисел представляется неразумным.
Возведение в степень Монтгомери
Использование алгоритма Монтгомери оправдывает себя при возведении числа в степень по модулю <math>a^{e} \mod{n}</math>.
Функция <math>ModExp(a,e,n)</math>
1. <math>\bar{a} = a \cdot r \mod{n}</math>
2. <math>\bar{x} = 1 \cdot r \mod{n}</math>
3. for i=j-1 downto 0
<math>\bar{x} = MonPro(\bar{x},\bar{x})</math>
if <math>e_{i}=1</math> then <math>\bar{x}=MonPro(\bar{x},\bar{a})</math>
4. return <math>x = MonPro(\bar{x},1)</math>
Возведение числа в степень битовой длины k алгоритмом «возводи в квадрат и перемножай» включает в себя от k до 2k умножений, где k имеет порядок сотен или тысяч бит. При использовании алгоритма возведения в степень Монтгомери объём дополнительных вычислений фиксирован (вычисления <math>n'</math>, <math>\bar{a}</math>, <math>\bar{x}</math> в начале и <math>MonPro(\bar{x},1)</math> в конце), а операция MonPro выполняется быстрее обычного умножения по модулю[1], поэтому алгоритм возведения в степень Монтгомери даст выигрыш в производительности по сравнению с алгоритмом «возводи в квадрат и перемножай».
Реализация алгоритма на JavaScript
function powMod(a, e, m) {
var r = 1;
while (e > 0) {
console.log('A='+a+', E='+e+', R='+r);
if ((e & 1) == 0) {
e = e >> 1;
a = (a * a) % m;
} else {
e = e - 1;
r = (r * a) % m;
}
}
console.log('A='+a+', E='+e+', R='+r);
return r;
}
Примечания
Литература
