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



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

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. t = \bar{a} \cdot \bar{b}
2. u = \cdot n ) / r
3. ifwhile u = u + n
4. return  u \mod n

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



Просмотров: 1775


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