在众多的加密算法中都需要进行幂的取模运算，比如在RSA算法中需要计算ne mod N，我们称之为幂模算法，其中：

• N=p*q（p，q为大素数）
• n为加密数据，n
• e为公钥，d为私钥，满足关系ed≡1 (mod (p-1)*(q-1))

其中n,e都是非常大的数，这样计算ne mod N就需要一些新方法，其计算方式也关系到RSA的效率问题。 对一般的幂模运算：ab mod m，存在下面三种算法：

1. 直接计算

先计算ab，再取模，这样很容易益处，在实际中基本不可行

2. 同余公式

设c是a除以m的余，即c=a-k*m，也可用同余表达式a≡c (mod m)表示，则可以证明：

    2.1 同余性质1：

    对任意整数b     ab≡bc (mod m) -----------(1)
    证明：         c=a mod m <=> a = km +c
        =>ab = k*b*m+bc => ab mod m = (k*b*m + bc)mod m = bc mod m     (1)式等价于：ab mod m =b* (a mod m) mod m，这非常适合递归计算。

    2.2 同余性质2

    a≡c (mod m) => a2≡c2 (mod m)--------------(2)     证明:         a=k*m+c =>a2=(km)2+2ckm+c2 =>a2 mod m =c2 mod m，即（2）成立

    2.3 基于性质1的算法

    特别地对幂取模计算可以递归使用（1）式 [java] view plaincopy

1. int mod(int a,int b,int m){  
2.     int result = 1;  
3.     for(int i=0;i
4.         result = (result*a) %m;  
5.     }  
6.     return result;  
7. }  

    如果指数b不大，上述方法很有效。但如前所述，一般在RSA算法中的指数b会很大（可以超过1024位），对如此巨大的一个数字做循环计算，时间开销将是不能接受的，因此需要继续从理论上挖掘计算幂取模的算法。

3.反复平方法

进一步研究指数b的二进制表示发现，对任意的整数b都可表示为：

• n表示b的实际二进制位数
• bi表示该位是0或1

因此，ab可表示为： 即用b的每一位表示a的每一项，而对任意相邻的两项存在平方关系，即： 因此我们构造下面的算法：

• 把b转换为二进制表示，并从右至左扫描其每一位（从低到高）
• 当扫描到第i位时，根据同余性质（2）计算a的第i项的模：
  
  base变量表示第i-1位时计算出的模，通过递归能很容易地确定所有位的模。
  
• 如果第i位为1，即bi=1,则表示该位需要参与模运算，计算结果 result = (result*base) mod m;其中result为前i-1次的计算结果；若bi=0，则表示a的第i项为1，不必参与模运算

代码如下： [java] view plaincopy

1. int mod(int a,int b,int m){  
2.     int result = 1;  
3.     int base = a;  
4.     while(b>0){  
5.          if(b & 1==1){  
6.             result = (result*base) % m;  
7.          }  
8.          base = (base*base) %m;  
9.          b>>>=1;  
10.     }  
11.     return result;  
12. }  

这其中有几个点要理解：

• base记录了a的每项的模，无论b在该位是0还是1，该结果都记录，目的是给后续位为1的项使用，计算方式是前一结果的平方取模，这也是反复平方法的由来
• result只记录了位为1的项的模结果，该计算方式使用了同余性质1
• 通过地把a使用二进制表示，并结合同余性质1，2，巧妙地化解了大数取模的运算。对1024位这样的大数，也最多进行1024次循环便可计算模值，性能非常快。

该方法是许多西方数学家努力的结果，通常也称为Montgomery算法。

4. 参考资料

【1】http://en.wikipedia.org/wiki/Modular_exponentiation 【2】初等数论 转载自http://blog.csdn.net/chen77716/article/details/7093600