Montgomery 模乘

Montgomery 模乘将数字变换到 Montgomery 数域，使得在 Montgomery 数域计算 \(ab\bmod N\) 是容易的，最后从 Montgomery 数域将数字变换回来。

由于需要两次变换，Montgomery 乘法比 Barrett 乘法慢一点；但如果需要大量计算，由于中间过程可以全部在 Montgomery 数域完成，Montgomery 乘法这时会更快。

与 Barrett 约简类似，Montgomery 乘法也需要固定 \(N\)，同时提供除以 \(R\) 的快速计算，这里还要求 \((N,R)=1,R>N\)。

Montgomery 形式

一个数 \(x\) 在 \(\bmod N\) 意义下的 Montgomery 形式就是 \(xR\bmod N\)，可以发现，由于分配律的存在，Montgomery 形式的加法和减法可以直接处理。

但是，如果我们将两个 Montgomery 数做乘法，我们发现结果会多一个 \(R\)。

Montgomery 约简

考虑消去这个 \(R\)。

令 \(-N\) 在 \(\bmod R\) 意义下的乘法逆元为 \(t\)，\(R\) 在 \(\bmod N\) 意义下的逆元为 \(R^{-1}\)，记 \(y=xt\bmod R\)，则 \(xR^{-1}\equiv\dfrac{x+yN}{R}\pmod N\)。

留给读者自证。

由于 \(\bmod R\) 可以快速计算，整个过程可以快速计算。

上面这个过程被称为 Montgomery 约简。

进入 Montgomery 数域可以实现为将原数乘 \(R^2\bmod N\) 再做 Montgomery 约简，离开 Montgomery 数域直接约简即可。

需要指出约简过程中 \(\dfrac{x+yN}{R}\lt\left\lfloor\dfrac{x}{R}\right\rfloor+M\)，通常 \(x<N^2\)，因此约简后值域为 \([0,2N)\)，需要再做一次比较运算。