- Алгоритм Монтгомери
-
Алгоритм Монтгомери — приём, позволяющий ускорить выполнение операций умножения и возведения в квадрат, необходимых при возведение числа в степень по модулю, когда модуль велик (порядка сотен бит). Был предложен в 1985 году Питером Монтгомери.
По данным целым числам a, b < n, r, НОД алгоритм Монтгомери вычисляет
Умножение Монтгомери
Положим .
Определим n-остаток (n-residue) числа как .
Алгоритм Монтгомери использует свойство, что множество является полной системой вычетов, то есть содержит все числа от 0 до n-1.
MonPro вычисляет . Результат является n-остатком от , так как
Определим n' так, что . и можно вычислить с помощью расширенного алгоритма Евклида.
Функция
1. 2. 3. while 4. return
Операции умножения и деления на r выполняются очень быстро, так как при представляют собой просто сдвиги бит. Таким образом алгоритм Монтгомери быстрее обычного вычисления , которое содержит деление на n. Однако вычисление n' и перевод чисел в n-остатки и обратно — трудоёмкие операции, вследствие чего применять алгоритм Монтгомери при вычислении произведения двух чисел представляется неразумным.
Возведение в степень Монтгомери
Использование алгоритма Монтгомери оправдывает себя при возведении числа в степень по модулю .
Функция
1. 2. 3. for i=j-1 downto 0 if then 4. return
Возведение числа в степень битовой длины k алгоритмом «возводи в квадрат и перемножай» включает в себя от k до 2k умножений, где k имеет порядок сотен или тысяч бит. При использовании алгоритма возведения в степень Монтгомери объём дополнительных вычислений фиксирован (вычисления , , в начале и в конце), а операция MonPro выполняется быстрее обычного умножения по модулю[1], поэтому алгоритм возведения в степень Монтгомери даст выигрыш в производительности по сравнению с алгоритмом «возводи в квадрат и перемножай».
Литература
Analyzing and Comparing Montgomery Multiplication Algorithms
- A. Menezes, P. van Oorschot, S. Vanstone. Chapter 14. Efficient Implementation // Handbook of Applied Cryptography. — CRC-Press, 1996. — 816 p. — (Discrete Mathematics and Its Applications). — ISBN 0-8493-8523-7
Категории:- Теоретико-числовые алгоритмы
- Компьютерная арифметика
Wikimedia Foundation. 2010.