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

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

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

$MonPro(a,b) = a \cdot b \cdot r^{-1} \mod{n}$

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

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

Определим n-остаток (n-residue) числа $a < n$ как $\bar{a} = a \cdot r \mod{n}$.

Алгоритм Монтгомери использует свойство, что множество $\{ a \cdot r \mod{n} \mid 0 \leqslant a \leqslant n-1 \}$ является полной системой вычетов, то есть содержит все числа от 0 до n-1.

MonPro вычисляет $\bar{c} = \bar{a} \cdot \bar{b} \cdot r^{-1} \mod{n}$. Результат является n-остатком от $c = a \cdot b \mod{n}$, так как

$\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}$

Определим n' так, что $r \cdot r^{-1} - n \cdot n' = 1$. $r^{-1}$ и $n'$ можно вычислить с помощью расширенного алгоритма Евклида.

Функция $MonPro(\bar{a},\bar{b})$

1. $t = \bar{a} \cdot \bar{b}$
2. $u = (t + (t \cdot n' \mod{r} ) \cdot n ) / r$
3. while $(u<0) u=u+n$
4. return  $u \mod n$

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

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

Использование алгоритма Монтгомери оправдывает себя при возведении числа в степень по модулю $a^{e} \mod{n}$.

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

1. $\bar{a} = a \cdot r \mod{n}$
2. $\bar{x} = 1 \cdot r \mod{n}$
3. for i=j-1 downto 0
     $\bar{x} = MonPro(\bar{x},\bar{x})$
     if $e_{i}=1$ then $\bar{x}=MonPro(\bar{x},\bar{a})$
4. return $x = MonPro(\bar{x},1)$

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

Литература

1. ↑ Analyzing and Comparing Montgomery Multiplication Algorithms

Analyzing and Comparing Montgomery Multiplication Algorithms

• A. Menezes, P. van Oorschot, S. Vanstone. Chapter 14. Efficient Implementation // Handbook of Applied Cryptography. — CRC-Press, 1996. — 816 p. — (Discrete Mathematics and Its Applications). — ISBN 0-8493-8523-7