В чем заключается суть метода Монтгомери при умножении больших чисел?

Суть метода Монтгомери при умножении больших чисел заключается в том, что он позволяет ускорить выполнение операций умножения и возведения в квадрат, необходимых при возведении числа в степень по модулю, когда модуль велик (порядка сотен бит). ru.wikipedia.org ru.ruwiki.ru

Алгоритм Монтгомери был предложен в 1985 году Питером Монтгомери. ru.wikipedia.org Он работает следующим образом: сначала преобразует множители в пространство Монтгомери, где модульное умножение можно выполнить дёшево, а затем преобразует их обратно, когда нужны их фактические значения. en.algorithmica.org

В приложениях обычно берётся r = 2^k, так как в этом случае деление с остатком и умножение на r, используемые внутри алгоритма, происходят быстро. ru.wikipedia.org