蒙哥马利算法

求 \(a\;mod\;N\)时，最容易想到的方法就是：如果\(a<N\)获得取模结果即为\(a\)，如果\(a*b>N\),那么就需要用到除法\(a \div N = c\;余 \;n\)，获得结果为余数\(n\)。因为除法在计算机当中效率非常低，所以采用普通算法计算大数取模（\(a\)远远大于 \(N\)）时，会因为使用到除法导致耗时非常长。

那如何避免使用除法，以提高大数取模的效率，蒙哥马利算法提出了对应的方法。

蒙哥马利算法

模逆元

如果 \(ab\;mod\;N=1\)，则称\(b\)为\(a\)的模\(N\)逆元（inverse），记为\(a^{-1}\)。

蒙哥马利形式

设\(N>1\)，找一个数\(R\)，需要满足：

1. \(R>N\)

2. \(R\)与\(N\)的最大公约数为 1，即：\(gcd(R,N)=1\)

3. 为了计算方便，\(R\)应为\(2\)的幂，假设\(2^k=R\)

令\(a'= aR\;mod\;N\)，这种形式称为蒙哥马利形式。

有了这个形式之后，就可以“绕路”来求\(ab\;mod\;N\)的值，通过“绕路”可以避免除法。

蒙哥马利约简

已有蒙哥马利形式是：\(aR\;mod\;N\)，蒙哥马利约简就是想办法将： \(aR\;mod\;N\)转化为\(a\;mod\;N\)。

我们令\(x=aR\)，则\(\frac{x}{R}\;mod\;N=\frac{aR}{R}\;mod\;N=a\;mod\;N\)。这里乍看起来好像有点多此一举，但其实不然，因为\(R\)是\(2\)的幂，所以除以\(R\)在计算机中处理时可以使用移位操作来处理，这样就可以先计算\(aR\)然后对获得的结果进行移位操作即可（避免了除法）。

但有个新问题，移位操作时可能会丢失一些二进制位，例如：\(\frac{7}{2^2}\)是将\(7=0000\;0111\)右移2位变为\(0000\;0001\)，这里丢失了一些二级制的低位值，本来\(\frac{7}{2^2}=1.75\)，而我们移位得到的结果却是\(1\)。

那如何避免这个问题？只要除数是被除数的倍数即可，例如：\(\frac{8}{2^2}=\frac{2^3}{2^2} =0000\;1000 \;右移2位\)\(=0000\;0010=2\)

那么新的问题就变成了，如何将\(\frac{x}{R}\)里面的\(x\)转化为\(R\)的倍数，同时还不影响最终的计算结果？

让\(x+mN\)即可（\(m\)是一个我们后面要计算的值），因为\((x+mN)\;mod\;N=(x\;mod\;N+mN\;mod\;N)\;mod\;N=(x\;mod\;N+0)\;mod\;N=x\;mod\;N\)，所以给\(x\)加上\(mN\)不会影响最终的计算结果。

为什么要给\(x+mN\)呢？

骚操作来了！！！

因为\(gcd(R,N)=1\)，根据扩展的欧几里得算法有：

1. \(0 < R⁻¹ < N\) //\(R^{-1}\)是\(R\)关于\(N\)的模逆元

2. \(0 < (-N)⁻¹ < R\) //\((-N)⁻¹\)是\(-N\)关于\(R\)的模逆元

3. \(R * R⁻¹ - N * (-N)⁻¹ = 1\)

有了这些等式，我们就可以来求\(m\)的值：

因为：\((x+mN)\;mod\;R = 0\;mod\;R\)