Об алгоритме удалось найти только статью на Википедии, но там написано всё непонятно для кого и непонятно кем. Поскольку я не очень силён в теории вычетов и дискретном логарифмировании, прошу помочь разобраться с реализацией, можно приводить примеры на языках 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
Или это и есть алгоритм?
Вопрос буду дополнять по мере разбора.
a*b = a+a+a...+a b раз
и спрашивать, что это за числаa
иb
и откуда их брать? Или - откуда братьa
иb
при решении уравненияax=b
? Применяется это все для вычисления произведенияab
по модулюn
.a
наb
по модулюn
. Не непосредственно, а как именно - описано там же, в Википедии.