175
правок
Изменения
Нет описания правки
Положим <tex>r=2^k</tex>.
Определим ''n''{{---}}остаток (''n''-residue) числа <tex>a < n</tex> как <tex>\bar{a} = a \cdot r \mod{n}</tex>.
Алгоритм Монтгомери использует свойство, что множество <tex>\{ a \cdot r \mod{n} \mid 0 \leqslant a \leqslant n-1 \}</tex> является [[Сравнения, система вычетов, решение линейных систем по модулю|полной системой вычетов]], то есть содержит все числа от ''0'' до ''n-1''.
MonPro вычисляет <tex>\bar{c} = \bar{a} \cdot \bar{b} \cdot r^{-1} \mod{n}</tex>. Результат является n{{---}}остатком от <tex>c = a \cdot b \mod{n}</tex>, так как
<tex>\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}</tex>
3. '''if''' <tex>u > n</tex> '''then return''' <tex>u-n</tex> '''else return''' <tex>u</tex>
Операции умножения и деления на r выполняются очень быстро, так как при <tex>r=2^{k}</tex> представляют собой просто сдвиги бит. Таким образом алгоритм Монтгомери быстрее обычного вычисления <tex>a \cdot b \mod{n}</tex>, которое содержит деление на n. Однако вычисление n' и перевод чисел в n{{---}}остатки и обратно — трудоёмкие операции, вследствие чего применять алгоритм Монтгомери при вычислении произведения двух чисел представляется неразумным.
== Возведение в степень Монтгомери ==
