Montgomery模乘

由于模运算非常慢，因此在实现RSA等算法时，引入了Montgomery模乘将模运算简化成了减法运算来进行，加快了模运算进行的速度。

问题的提出

加速 $xy \ mod \ N$ ，使得运算中不产生模 $N$ 运算。 $x, y$ 保证 $x, y < N$。

Montgomery约减

定义Montgomery约减 $REDC(T) = TR^{-1} \ mod \ N$ 。其中 $R > N$ 且 $gcd(N, R) = 1$ ， $R^-1$ 为 $R$ 在模 $N$ 意义下的逆元，即 $RR^{-1} \equiv 1 (mod \ N)$ 。取 $N’$ 使得 $RR^{-1} - NN’ = 1$ ，由模运算的定义这样的 $N’$ 显然存在。算法的输入 $T$ 保证 $T < NR$。

Montgomery约减的算法描述如下：

首先来证明 $t$ 是一个整数：由 $NN’ = RR^{-1} -1$ 得 $mN \equiv TNN’ \equiv -T (mod \ R)$，故 $T + mN \equiv 0 (mod \ R)$，则 $t$ 是一个整数。其次证明 $t < 2N$，即用一次减法必然能得到要求的解： $m < R$ ，故 $mN < NR$ ，结合前提 $T < NR$ , 有 $mN + T < 2NR$ ， $t = \frac{mN + T}{R} < 2N$ 。

结果的正确性说明：

$$ \begin{align*} t &\equiv \frac{T + mN}{R} \\ &\equiv \frac{T + N((T \ mod \ R)N’ \ mod \ R)}{R} \\ &\equiv \frac{T + N(TN’ mod R)}{R} \\ &\equiv \frac{T + TNN’ - \lfloor \frac{TN’}{R} \rfloor RN}{R} &\\ &\equiv \frac{T + TNN’}{R} \\ &\equiv \frac{T(1 + NN’)}{R} \\ &\equiv \frac{TRR^{-1}}{R} \\ &\equiv TR^{-1} (mod \ N) \end{align*} $$