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

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

По данным целым числам a, b < n, r, НОД[math]\displaystyle{ (r,n)=1 }[/math] алгоритм Монтгомери вычисляет

[math]\displaystyle{ MonPro(a,b) = a \cdot b \cdot r^{-1} \mod{n} }[/math]

В приложениях обычно берётся [math]\displaystyle{ r=2^k }[/math], так как в этом случае деление с остатком и умножение на [math]\displaystyle{ r }[/math], используемые внутри алгоритма, происходят быстро.

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

Определим n-остаток (n-residue) числа [math]\displaystyle{ a \lt n }[/math] как [math]\displaystyle{ \bar{a} = a \cdot r \mod{n} }[/math].

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

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

[math]\displaystyle{ \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]\displaystyle{ r \cdot r^{-1} - n \cdot n' = 1 }[/math]. [math]\displaystyle{ r^{-1} }[/math] и [math]\displaystyle{ n' }[/math] можно вычислить с помощью расширенного алгоритма Евклида.

Функция [math]\displaystyle{ MonPro(\bar{a},\bar{b}) }[/math]

1. [math]\displaystyle{ t = \bar{a} \cdot \bar{b} }[/math]
2. [math]\displaystyle{ u = (t + (t \cdot n' \mod{r} ) \cdot n ) / r }[/math]
3. while [math]\displaystyle{ (u \gt = n) u = u - n }[/math]
4. return  [math]\displaystyle{ u }[/math]

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

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

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

Функция [math]\displaystyle{ ModExp(a,e,n) }[/math]

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

Возведение числа в степень битовой длины k алгоритмом «возводи в квадрат и перемножай» включает в себя от k до 2k умножений, где k имеет порядок сотен или тысяч бит. При использовании алгоритма возведения в степень Монтгомери объём дополнительных вычислений фиксирован (вычисления [math]\displaystyle{ n' }[/math], [math]\displaystyle{ \bar{a} }[/math], [math]\displaystyle{ \bar{x} }[/math] в начале и [math]\displaystyle{ MonPro(\bar{x},1) }[/math] в конце), а операция 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