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

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

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

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

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

Умножение Монтгомери[править | править код]

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

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

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

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

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

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

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

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

Возведение в степень Монтгомери[править | править код]

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

Функция ${\displaystyle ModExp(a,e,n)}$

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

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

Примечания[править | править код]

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

• Analyzing and Comparing Montgomery Multiplication Algorithms
• Menezes A. J., Oorschot P. v., Vanstone S. A. Chapter 14. Efficient Implementation // Handbook of Applied Cryptography (англ.) — CRC Press, 1996. — 816 p. — (Discrete Mathematics and Its Applications) — ISBN 978-0-8493-8523-0

Это заготовка статьи по математике. Помогите Википедии, дополнив её.