蒙哥马利大整数模幂算法

  前几天写了一篇博客《25行代码实现完整的RSA算法》，是关于用Python代码实现一个完整的RSA算法的代码，整个代码中最核心、最浪费时间的代码部分就是关于求解大整数模幂算法这里。整个算法也叫“蒙哥马利幂模”算法。
  首先简单介绍一下蒙哥马利相关的几个算法，具体详细介绍可以参考《蒙哥马利算法详解》。蒙哥马利算法并不是一个独立的算法，而是三个相互独立又相互联系的算法集合，其中包括：

• 蒙哥马利乘模，是用来计算x⋅y(modN)" role="presentation">x⋅y(modN)$x\cdot y(modN)$
• 蒙哥马利约减，是用来计算t⋅ρ−1(modN)" role="presentation">t⋅ρ−1(modN)$t\cdot {\rho }^{-1}(modN)$
• 蒙哥马利幂模，是用来计算xy(modN)" role="presentation">xy(modN)$x^y(modN)$

  在这三个算法中，蒙哥马利幂模是RSA加密算法的核心部分。本篇文章为了简单起见就不介绍前两个“蒙哥马利乘模”和“蒙哥马利约减”算法了。主要介绍第三个“蒙哥马利幂模”的计算方法过程，以及通过一个小例子进行说明这个算法的具体计算过程，至于证明方法我就不在这里介绍，大家只要能看到这个例子以后，能把代码写出来就能写完整的RSA算法了。如果想看已经实现的代码请参考这里，或者这里。在这两篇博文里都有完整的代码实现方法。下面介绍“蒙哥马利幂模”的详细计算过程：
  RSA公钥密码的加密算法与解密算法都要计算“模幂乘运算”ab(modN)" role="presentation">ab(modN)$a^b(modN)$。
设b的二进制数字表示为br−1...b1b0" role="presentation">br−1...b1b0$b_{r-1}...b_1{b}_0$，即：
      b=b0+b1×2+...+br−1×2r−1" role="presentation">b=b0+b1×2+...+br−1×2r−1$b=b_0+b_1\times 2+...+b_{r-1}\times 2^{r-1}$。
于是：
      ab≡ab0×(a2)b1×...×(a2r−1)br−1(modN)" role="presentation">ab≡ab0×(a2)b1×...×(a2r−1)br−1(modN)$a^b\equiv a^{b_0}\times (a^2{)}^{b_1}\times ...\times (a^{2^{r-1}}{)}^{b_{r-1}}(modN)$
令A0=a" role="presentation">A0=a$A_0=a$，Ai≡(Ai−1)2(modN)" role="presentation">Ai≡(Ai−1)2(modN)$A_i\equiv (A_{i-1}{)}^2(modN)$，i = 1， 2… r - 1，则有：
    ab≡A0b0×A1b1×...×Ar−1br−1(modN)" role="presentation">ab≡A0b0×A1b1×...×Ar−1br−1(modN)$a^b\equiv {A_0}^{b_0}\times {A_1}^{b_1}\times ...\times {A_{r-1}}^{b_{r-1}}(modN)$
其中，在这里
Aibi={Ai,若bi=11,若bi=0i=0,1...r−1" role="presentation">Aibi={Ai,1,若bi=1若bi=0i=0,1...r−1