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

Компьютеры - Алгоритм Монтгомери - Возведение в степень Монтгомери

Использование алгоритма Монтгомери оправдывает себя при возведении числа в степень по модулю .

Функция ModExp

1. 
2. 
3. for i=j-1 downto 0
     
     if ei = 1 then 
4. return 

Возведение числа в степень битовой длины k алгоритмом «возводи в квадрат и перемножай» включает в себя от k до 2k умножений, где k имеет порядок сотен или тысяч бит. При использовании алгоритма возведения в степень Монтгомери объём дополнительных вычислений фиксирован" src="http://upload.wikimedia.org/math/f/a/2/fa2598d7a16937f69545151147c268ed.png" /> в конце), а операция MonPro выполняется быстрее обычного умножения по модулю, поэтому алгоритм возведения в степень Монтгомери даст выигрыш в производительности по сравнению с алгоритмом «возводи в квадрат и перемножай».