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

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

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

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

В приложениях обычно берётся $r=2^k$, так как в этом случае деление с остатком и умножение на $r$, используемые внутри алгоритма, происходят быстро.

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

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

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

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

$\overline{c}=\overline{a}\cdot \overline{b}\cdot r^{-1}modn=a\cdot r\cdot b\cdot r\cdot r^{-1}modn=c\cdot rmodn$

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

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

1. $t=\overline{a}\cdot \overline{b}$
2. $u=(t+(t\cdot n^{\prime }modr)\cdot n)/r$
3. while $(u>=n)u=u-n$
4. return  $u$

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

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

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

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

1. $\overline{a}=a\cdot rmodn$
2. $\overline{x}=1\cdot rmodn$
3. for i=j-1 downto 0
     $\overline{x}=MonPro(\overline{x},\overline{x})$
     if $e_i=1$ then $\overline{x}=MonPro(\overline{x},\overline{a})$
4. return $x=MonPro(\overline{x},1)$

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

Реализация алгоритма на 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;
}

Литература

• Analyzing and Comparing Montgomery Multiplication Algorithms
• Шаблон:Source