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

Интернет магазин китайских планшетных компьютеров

Компьютеры - Алгоритм Монтгомери

23 января 2011

Оглавление:
1. Алгоритм Монтгомери
2. Возведение в степень Монтгомери

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

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

$MonPro = a \cdot b \cdot r^{-1} \mod{n}$

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

Положим r = 2.

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

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

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

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

Функция $MonPro$

1. 
2. 
3. ifwhile u = u + n
4. return

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

<<< Алгоритм Евклида

Компьютерное аппаратное обеспечение
Вычислительные комплексы
Компьютерные данные
Компьютерные журналы
Классы компьютеров
Компьютеры

Программное обеспечение
Производители компьютеров
Профессии в ИТ
Системное администрирование
Компьютерный сленг
Списки компьютерных терминов

Человеко-компьютерное взаимодействие