一、背景： RSA算法里头经常要用到“求x的n次方模m”这样的过程，通常使用O(log(n))的模重复平方算法来实现，提高效率。在《数论》和《信息安全数学基础》中也会介绍。 二、在介绍模重复平方算法之前，我们需要了解模的基本运算，如下（来着百度百科）：

基本概念

给定一个正整数    ，任意一个整数    ，一定存在等式    ； 其中    、    是整数，且    ，称    为    除以    的商，    为    除以    的余数。   对于正整数和整数    ,    ，定义如下运算： 取模运算：a % p（或a mod p），表示a除以p的余数。 模p加法：(a + b) % p ，其结果是a+b算术和除以p的余数，也就是说，(a+b) = kp +r，则(a + b) % p = r。 模p减法：(a-b) % p ，其结果是a-b算术差除以p的余数。 模p乘法：(a * b) % p，其结果是 a * b算术乘法除以p的余数。 说明： 1.同余式：正整数a，b对p取模，它们的余数相同，记做 a ≡ b % p或者a ≡ b (mod p)。 2. n % p得到结果的正负由被除数n决定,与p无关。例如：7%4 = 3， -7%4 = -3， 7%-4 = 3， -7%-4 = -3。

基本性质

（1）若p|(a-b)，则a≡b (% p)。例如 11 ≡ 4 (% 7)， 18 ≡ 4(% 7) （2）(a % p)=(b % p)意味a≡b (% p) （3）对称性：a≡b (% p)等价于b≡a (% p) （4）传递性：若a≡b (% p)且b≡c (% p) ，则a≡c (% p)

运算规则

模运算与基本四则运算有些相似，但是除法例外。其规则如下： (a + b) % p = (a % p + b % p) % p （1） (a - b) % p = (a % p - b % p) % p （2） (a * b) % p = (a % p * b % p) % p（3） (a^b) % p = ((a % p)^b) % p （4） 结合律： ((a+b) % p + c) % p = (a + (b+c) % p) % p （5） ((a*b) % p * c)% p = (a * b*c) % p （6）// (a%p*b)%p=(a*b)%p 交换律： (a + b) % p = (b+a) % p （7） (a * b) % p = (b * a) % p （8） 分配律： ((a +b)% p * c) % p = ((a * c) % p + (b * c) % p) % p （9） 重要定理： 若a≡b (% p)，则对于任意的c，都有(a + c) ≡ (b + c) (%p)；（10） 若a≡b (% p)，则对于任意的c，都有(a * c) ≡ (b * c) (%p)；（11） 若a≡b (% p)，c≡d (% p)，则 (a + c) ≡ (b + d) (%p)，(a - c) ≡ (b - d) (%p)， (a * c) ≡ (b * d) (%p)，(a / c) ≡ (b / d) (%p)； （12） 三、模重复平方计算法： 在模算术计算中，常常要对大整数m和n，计算b^n (mod m). 如果用递归，则可以得到： b^n (mod m) = b^n % m  = b*b^(n-1) % m . 根据模的运算规则，可以进一步得到：
b*b^(n-1) % m = b*(b^(n-1) % m) % m     = b* (b^(n-1) (mod m)) (mod m).  所以有：
b^n (mod m) = b* (b^(n-1) (mod m)) (mod m). 得到b^n (mod m)的递归公式为： func(b, n, m) = b* func(b, n-1, m) % m. 至此模重复平方算法的递归代码就很容易写出： // 底数b，指数n，对m模 int squreMod(int b, int n, int m) { if(0 == n) return 1; return b* squreMod(b, n-1, m) % m; }
模重复计算法的递归实现，思路简单清晰，但是因为递归层次过深，同时需要执行n-1次乘法，所以很难用于实际应用之中，一般我们会使用非递归来实现。 思路讲解（时间复杂度O(logn)）：

注：1. 每次进行 a*b (mod m) 时，都在乘法运算之后进行了一次对m模，这样可以和整个公式最后的mod m统一，方便循环处理。 2. b1 已经对m进行模运算了。相当于每个因子都进行了一次模m。例如，设a=1，则b1*b2*b3 (mod m) = a*(b1%m) * b2 * b3 % m; 令a1 = (a*(b1%m))%m, 则 a*(b1%m) * b2 * b3 % m = a1*b2*b3 % m. 以此类推， 令a2 = (a1*(b2%m)) % m, a1*b2*b3 % m = a2*b3 % m。这样就可以将原始公式层层缩减。直到最后：ak 就是b^n (mod m)的值。 其中：a1 = (a*(b1%m)) %m，可以相当于本例中a1≡a0*b1^n1 (mod m)。也即下面（2）中的a1.





c实现源码： https://github.com/yangxt225/powerMod