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

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

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

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