Описание тега montgomery-multiplication

Описание тега Вопросы с тегом

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

Алгоритм редукции Монтгомери Redc(T) вычисляет TR^{-1} mod {N} следующим образом:

m := (k (T mod R)) mod {R}
t := (T + mN)/R
if  t >= N return t - N else return t.

Используя этот метод для расчета c обычно менее эффективен, чем наивное умножение и сокращение, так как стоимость преобразований в и из представления остатка (умножения на R а также R^{-1} modulo N) перевешивают экономию от этапа сокращения.

Преимущество этого метода становится очевидным при работе с последовательностью умножений, необходимой для модульного возведения в степень (например, возведения в степень возведением в квадрат).

Многие важные криптосистемы, такие как RSA и DSA, основаны на арифметических операциях, таких как умножение по модулю большого числа. Классический метод вычисления модульного произведения включает в себя сначала умножение чисел, как если бы они были целыми числами, а затем взятие модуля результата. Однако модульное сокращение требует больших вычислительных ресурсов, что эквивалентно делению двух чисел.

Ситуация еще хуже, когда алгоритм требует модульного возведения в степень.