Умножение по Монтгомери - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:26:58Z

rollbackEdits.php mass rollback

91.212.153.123 в 04:53, 1 сентября 2022

2022-09-01T04:53:12Z

Shersh в 12:21, 6 мая 2014

2014-05-06T12:21:26Z

Bochkarev в 22:11, 11 октября 2010

2010-10-11T22:11:14Z

192.168.0.2: Новая страница: «'''Алгоритм Монтгомери''' — приём, позволяющий ускорить выполнение операций умножения и во…»

2010-10-08T19:32:32Z

Новая страница: «'''Алгоритм Монтгомери''' — приём, позволяющий ускорить выполнение операций умножения и во…»

Новая страница

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

По данным целым числам ''a, b < n'', ''r'', [[Наибольший общий делитель|НОД]]<tex>(r,n)=1</tex> алгоритм Монтгомери вычисляет

<tex>MonPro(a,b) = a \cdot b \cdot r^{-1} \mod{n}</tex>

== Умножение Монтгомери ==
Положим <tex>r=2^k</tex>.

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

Алгоритм Монтгомери использует свойство, что множество <tex>\{ a \cdot r \mod{n} \mid 0 \leqslant a \leqslant n-1 \}</tex> является [[Сравнения, система вычетов, решение линейных систем по модулю|полной системой вычетов]], то есть содержит все числа от ''0'' до ''n-1''.

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

<tex>\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}</tex>

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

Функция <tex>MonPro(\bar{a},\bar{b})</tex>
1. <tex>t = \bar{a} \cdot \bar{b}</tex>
2. <tex>u = (t + (t \cdot n' \mod{r} ) \cdot n ) / r</tex>
3. '''if''' <tex>u > n</tex> '''then return''' <tex>u-n</tex> '''else return''' <tex>u</tex>

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

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

Функция <tex>ModExp(a,e,n)</tex>
1. <tex>\bar{a} = a \cdot r \mod{n}</tex>
2. <tex>\bar{x} = 1 \cdot r \mod{n}</tex>
3. for i=j-1 downto 0
<tex>\bar{x} = MonPro(\bar{x},\bar{x})</tex>
if <tex>e_{i}=1</tex> then <tex>\bar{x}=MonPro(\bar{x},\bar{a})</tex>
4. return <tex>x = MonPro(\bar{x},1)</tex>

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

← Предыдущая		Версия 12:21, 6 мая 2014
Строка 41:		Строка 41:
	операция MonPro выполняется быстрее обычного умножения по модулю,		операция MonPro выполняется быстрее обычного умножения по модулю,
	поэтому алгоритм возведения в степень Монтгомери даст выигрыш в производительности по сравнению с [[Быстрое возведение в степень\|алгоритмом быстрого возведения в степень]].		поэтому алгоритм возведения в степень Монтгомери даст выигрыш в производительности по сравнению с [[Быстрое возведение в степень\|алгоритмом быстрого возведения в степень]].
		+
		+	== Ссылки ==
		+	[http://guan.cse.nsysu.edu.tw/note/montg.pdf Montgomery multiplication]

@@ Строка 1: / Строка 1: @@
-{| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
+'''Алгоритм Монтгомери''' — приём, позволяющий ускорить выполнение операций умножения и возведения в квадрат, необходимых при возведение числа в степень [[Сравнения, система вычетов, решение линейных систем по модулю|по модулю]], когда модуль велик (порядка сотен бит).
-|+
+Был предложен в 1985 году Питером Монтгомери.
 По данным целым числам ''a, b < n'', ''r'', [[Наибольший общий делитель|НОД]]<tex>(r,n)=1</tex> алгоритм Монтгомери вычисляет
@@ Строка 45: / Строка 24: @@
 . '''if''' <tex>u > n</tex> '''then return''' <tex>u-n</tex> '''else return''' <tex>u</tex>
-Операции умножения и деления на r выполняются очень быстро, так как при <tex>r=2^{k}</tex> представляют собой просто сдвиги бит. Таким образом алгоритм Монтгомери быстрее обычного вычисления <tex>a \cdot b \mod{n}</tex>, которое содержит деление на n. Однако вычисление n' и перевод чисел в n{{---}}остатки и обратно — трудоёмкие операции, вследствие чего применять алгоритм Монтгомери при вычислении произведения двух чисел представляется неразумным.
+Операции умножения и деления на r выполняются очень быстро, так как при <tex>r=2^{k}</tex> представляют собой просто сдвиги бит. Таким образом алгоритм Монтгомери быстрее обычного вычисления <tex>a \cdot b \mod{n}</tex>, которое содержит деление на n. Однако вычисление n' и перевод чисел в n{{---}}остатки и обратно — трудоёмкие операции, вследствие чего применять алгоритм Монтгомери при вычислении произведения двух чисел представляется неразумным.
 == Возведение в степень Монтгомери ==

@@ Строка 9: / Строка 9: @@
 Положим <tex>r=2^k</tex>.
-Определим ''n''-остаток (''n''-residue) числа <tex>a < n</tex> как <tex>\bar{a} = a \cdot r \mod{n}</tex>.
+Определим ''n''{{---}}остаток числа <tex>a < n</tex> как <tex>\bar{a} = a \cdot r \mod{n}</tex>.
 Алгоритм Монтгомери использует свойство, что множество <tex>\{ a \cdot r \mod{n} \mid 0 \leqslant a \leqslant n-1 \}</tex> является [[Сравнения, система вычетов, решение линейных систем по модулю|полной системой вычетов]], то есть содержит все числа от ''0'' до ''n-1''.
-MonPro вычисляет <tex>\bar{c} = \bar{a} \cdot \bar{b} \cdot r^{-1} \mod{n}</tex>. Результат является n-остатком от <tex>c = a \cdot b \mod{n}</tex>, так как
+MonPro вычисляет <tex>\bar{c} = \bar{a} \cdot \bar{b} \cdot r^{-1} \mod{n}</tex>. Результат является n{{---}}остатком от <tex>c = a \cdot b \mod{n}</tex>, так как
 <tex>\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}</tex>
@@ Строка 24: / Строка 24: @@
 . '''if''' <tex>u > n</tex> '''then return''' <tex>u-n</tex> '''else return''' <tex>u</tex>
-Операции умножения и деления на r выполняются очень быстро, так как при <tex>r=2^{k}</tex> представляют собой просто сдвиги бит. Таким образом алгоритм Монтгомери быстрее обычного вычисления <tex>a \cdot b \mod{n}</tex>, которое содержит деление на n. Однако вычисление n' и перевод чисел в n-остатки и обратно — трудоёмкие операции, вследствие чего применять алгоритм Монтгомери при вычислении произведения двух чисел представляется неразумным.
+Операции умножения и деления на r выполняются очень быстро, так как при <tex>r=2^{k}</tex> представляют собой просто сдвиги бит. Таким образом алгоритм Монтгомери быстрее обычного вычисления <tex>a \cdot b \mod{n}</tex>, которое содержит деление на n. Однако вычисление n' и перевод чисел в n{{---}}остатки и обратно — трудоёмкие операции, вследствие чего применять алгоритм Монтгомери при вычислении произведения двух чисел представляется неразумным.
 == Возведение в степень Монтгомери ==