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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

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

[править | править код]

Определим n-остаток (n-residue) числа как .

Алгоритм Монтгомери использует свойство, что множество является полной системой вычетов, то есть содержит все числа от 0 до n-1.

MonPro вычисляет . Результат является n-остатком от , так как

Определим n' так, что . и можно вычислить с помощью расширенного алгоритма Евклида.

Функция

1. 
2. 
3. while 
4. return  

При операции умножения и деления на выполняются очень быстро, так как представляют собой просто сдвиги бит, а при цикл в строчке 3 выполнится не более одного раза. Таким образом алгоритм Монтгомери быстрее обычного вычисления , которое содержит деление на n. Однако вычисление n' и перевод чисел в n-остатки и обратно — трудоёмкие операции, вследствие чего применять алгоритм Монтгомери при однократном вычислении произведения двух чисел представляется неразумным.

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

[править | править код]

Использование алгоритма Монтгомери оправдывает себя при возведении числа в степень по модулю .

Функция

1. 
2. 
3. for i=j-1 downto 0
     
     if  then 
4. return 

Возведение числа в степень битовой длины k алгоритмом «возводи в квадрат и перемножай» включает в себя от k до 2k умножений, где k имеет порядок сотен или тысяч бит. При использовании алгоритма возведения в степень Монтгомери объём дополнительных вычислений фиксирован (вычисления , , в начале и в конце), а операция 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;
}

Примечания

[править | править код]

Литература

[править | править код]