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

#c_sharp #cpp #c #алгоритм

Об алгоритме удалось найти только статью на Википедии, но там написано всё непонятно
для кого и непонятно кем. Поскольку я не очень силён в теории вычетов и дискретном
логарифмировании, прошу помочь разобраться с реализацией, можно приводить примеры на
языках c#, c, c++.

Сначала разбираемся с умножением.

Выдержки из статьи:


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


Алгоритм реализует умножение чисел по модулю (a*b) mod n.


  Положим r=2^k.
  
  Определим n-остаток (n-residue) числа a < n как a' = a * r mod n


Как я понял, нам нужно подобрать такое k, чтобы r > n.


  MonPro вычисляет c' = a' * b' * r^-1 mod n


Как посчитать b'?


  MonPro(a,b) = a * b * r^-1 mod n


Или это и есть алгоритм?

Вопрос буду дополнять по мере разбора.
    

Ответы

Ответ 1

Вот фотка из моего учебника (переписывать, честно, лень). Все понятно вроде (почти
код на Паскале). Надеюсю, Вам поможет. Обоснование, думаю, не надо?