Умножение по Монтгомери — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
Строка 1: Строка 1:
{| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
+
'''Алгоритм Монтгомери''' — приём, позволяющий ускорить выполнение операций умножения и возведения в квадрат, необходимых при возведение числа в степень [[Сравнения, система вычетов, решение линейных систем по модулю|по модулю]], когда модуль велик (порядка сотен бит).
|+
+
Был предложен в 1985 году Питером Монтгомери.
|-align="center"
 
|'''НЕТ ВОЙНЕ'''
 
|-style="font-size: 16px;"
 
|
 
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
 
 
 
Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
 
 
 
Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
 
 
 
Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
 
 
 
''Антивоенный комитет России''
 
|-style="font-size: 16px;"
 
|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
 
|-style="font-size: 16px;"
 
|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
 
|}
 
 
 
'''Алгоритм Монтгомери''' приём, позволяющий ускорить выполнение операций умножения и возведения в квадрат, необходимых при возведение числа в степень [[Сравнения, система вычетов, решение линейных систем по модулю|по модулю]], когда модуль велик (порядка сотен бит).
 
Был предложен в 1985 году Питером Монтгомери.
 
  
 
По данным целым числам ''a, b < n'', ''r'', [[Наибольший общий делитель|НОД]]<tex>(r,n)=1</tex> алгоритм Монтгомери вычисляет
 
По данным целым числам ''a, b < n'', ''r'', [[Наибольший общий делитель|НОД]]<tex>(r,n)=1</tex> алгоритм Монтгомери вычисляет
Строка 45: Строка 24:
 
  3. '''if''' <tex>u > n</tex> '''then return''' <tex>u-n</tex> '''else return''' <tex>u</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{{---}}остатки и обратно — трудоёмкие операции, вследствие чего применять алгоритм Монтгомери при вычислении произведения двух чисел представляется неразумным.
+
Операции умножения и деления на r выполняются очень быстро, так как при <tex>r=2^{k}</tex> представляют собой просто сдвиги бит. Таким образом алгоритм Монтгомери быстрее обычного вычисления <tex>a \cdot b \mod{n}</tex>, которое содержит деление на n. Однако вычисление n' и перевод чисел в n{{---}}остатки и обратно — трудоёмкие операции, вследствие чего применять алгоритм Монтгомери при вычислении произведения двух чисел представляется неразумным.
  
 
== Возведение в степень Монтгомери ==
 
== Возведение в степень Монтгомери ==

Текущая версия на 19:26, 4 сентября 2022

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

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

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

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

Положим [math]r=2^k[/math].

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

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

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

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

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

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

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

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

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

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

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

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

Ссылки

Montgomery multiplication