Центральный Дом Знаний - Алгоритм Монтгомери

Информационный центр "Центральный Дом Знаний"

Заказать учебную работу! Жми!



ЖМИ: ТУТ ТЫСЯЧИ КУРСОВЫХ РАБОТ ДЛЯ ТЕБЯ

      cendomzn@yandex.ru  

Наш опрос

Как Вы планируете отдохнуть летом?
Всего ответов: 903

Онлайн всего: 1
Гостей: 1
Пользователей: 0


Форма входа

Логин:
Пароль:

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

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

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

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

Положим r = 2k.

Определим n-остаток (n-residue) числа 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 − 1 и n' можно вычислить с помощью расширенного алгоритма Евклида.

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

1. t = \bar{a} \cdot \bar{b}

2. u = (t + (t \cdot n' \mod{r} ) \cdot n ) / r

3. if(u<0)while (u < 0)u = u + n

4. return u \mod n

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

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

Функция ModExp(a,e,n)

1. \bar{a} = a \cdot r \mod{n}

2. \bar{x} = 1 \cdot r \mod{n}

3. for i=j-1 downto 0

\bar{x} = MonPro(\bar{x},\bar{x})

if ei = 1 then \bar{x}=MonPro(\bar{x},\bar{a})

4. return x = MonPro(\bar{x},1)

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

Loading

Календарь

«  Сентябрь 2019  »
ПнВтСрЧтПтСбВс
      1
2345678
9101112131415
16171819202122
23242526272829
30

Архив записей

Друзья сайта

  • Заказать курсовую работу!
  • Выполнение любых чертежей
  • Новый фриланс 24