蒙哥马利算法
蒙哥马利算法
概述
蒙哥马利算法包括模乘、约减和模幂。其主要思路是：通过选择合适的参数\(R\)，将数转化为蒙哥马利形式，在该形式下除法可以用移位代替，从而简化了计算。进行模乘时，需要先将数转化为蒙哥马利形式，计算完毕后再转换回原形式，因此单次乘法开销较普通模乘大，但乘法数量多时，由于只需要在开始和结束时转换，因此效率很高。
算法
转换为蒙哥马利形式
设\(a\)、\(b\)为乘数，\(N\)为模数。首先需要寻找一个参数\(R\)，满足以下两个条件：①\(R>N\)；②\(gcd(R,N)=1\)，即\(R\)与\(N\)互质。将一个数转化为其蒙哥马利形式，只需乘以\(R\)再取模\(N\)，如\(a\)、\(b\)的蒙哥马利形式为：\(aR\bmod N\)和\(bR\bmod N\)，记作\(\overline a\)和\(\overline b\)。
对于程序设计来说\(R\)通常选择为2的次幂，这样除以\(R\)可以用移位来简化计算。另外以上转换并不会损失任何信息，因为\(R\)与\(N\)互质，转换前后的两个群是同构的。
以\(N=17\)，\(R=100\)为例：
| 原形式 | 转换 | 蒙哥马利形式 |
|---|---|---|
| \(3\) | \(3\times 100\bmod17=11\) | \(11\) |
| \(7\) | \(7\times 100\bmod17=3\) | \(3\) |
| \(15\) | \(15\times 100\bmod17=4\) | \(4\) |
蒙哥马利形式下的计算
蒙哥马利形式下加减法的结果是原形式下结果的蒙哥马利形式，因为： \[ \begin{align} \overline a+\overline b\equiv aR\bmod N+bR\bmod N\equiv (a+b)R\bmod N\equiv \overline{a+b}\pmod N\\ \overline a-\overline b\equiv aR\bmod N-bR\bmod N\equiv (a-b)R\bmod N\equiv \overline{a-b}\pmod N \end{align} \] 但乘法不一样，\(ab\)的蒙哥马利形式为\(\overline{ab}=abR\bmod N\)，而将蒙哥马利形式下的\(a\)和\(b\)相乘结果如下： \[ \overline a\times\overline b\equiv(aR\bmod N)(bR\bmod N)\equiv(abR)R\bmod N\ne\overline{ab}\pmod N \]
不难发现上式结果多了一个\(R\)，因此要得到\(\overline{ab}\)还得再除以\(R\)，即乘以\(R\)的逆元\(R^{-1}\)，由于\(R\)与\(N\)互质，逆元一定存在。
仍以\(N=17\)，\(R=100\)为例，设\(a=7\)，\(b=15\)：因为\(100\times8\bmod17=1\)，所以\(R\)的逆元\(R^{-1}=8\)。原形式的乘法\(ab\bmod N=7\times15\bmod17=3\)，蒙哥马利形式的乘法\(\overline{ab}=\overline a\overline bR^{-1}\bmod N=3\times4\times8\bmod17=11\)，恰好对应\(3\)的蒙哥马利形式。
REDC算法
上节中计算蒙哥马利乘法需要乘以\(R^{-1}\)再约减，虽然这样计算没有问题，但约减的计算量很大，因此有了这节的蒙哥马利约减算法，简称REDC。直接看算法：
输入：\(R\)，\(N\)，\(N'\)（满足\(N'N\equiv-1\pmod R\)），要约减的数\(T\)（\(T\in[0,RN-1]\)）。
输出：\(TR^{-1}\bmod N\)
m = (T mod R)N' mod R
t = (T + mN) / R
if t >= N
return t - N
else
return t第一行计算参数\(m\)，这样可以保证第二行的\(T+mN\)可以被\(R\)整除，因为有： \[ \begin{align} T+mN&\equiv T+((T\bmod R)N'\bmod R)N\\ &\equiv T+TN'N\\ &\equiv T-T=0\pmod R \end{align} \] 再来看\(t\)的值： \[ t\equiv(T+mN)R^{-1}\equiv TR^{-1}+mNR^{-1}\equiv TR^{-1}\pmod N \] 因此\(t\)与最终要求的\(TR^{-1}\)在模\(N\)下是同余的。由于\(m\in[0,R-1]\)，有\(T+mN\in[0,RN-1+N(R-1)]<2RN\)，所以\(t\in[0,2N-1]\)，只需至多一次减法即可将\(t\)约减至\([0,N-1]\)，对应算法中的if-else判断逻辑。