大家好，我是小环，我来为大家解答以上问题。快速幂算法，快速幂很多人还不知道，现在让我们一起来看看吧！

1、解释一下a^b mod c： a^b mod c=a^(f[0]*2^0+f[1]*2^1+f[2]*2^2...f[t]*2^t) 因为 a*b mod c= ((a mod c) *b) mod c 所以 a^b mod c=(((f[0]*2^0 mod c)*f[1]*2^1 mod c)......*f[t]*2^t mod c) 用这种方法解决a^b mod c 时间复杂度 2^t<=b<2^(t+1) t<=log(2)b

2、具体如下:="" n可以直接计算，没有必要先算m^e。

3、="" t="log(2)b" 事实上，m^e="" 因为="" 所以="" 时间复杂度比直接循环求a^b大大的降低了="" 模取幂运算="" 设是整数b的二进制表示（即b的二进制有k+1位，b[k]是最 高位），下列过程随着c的值从0到b成倍增加，最终计算出a^c mod n Modular-Exponentiation(a, b, n) 1. c ← 0 2. d ← 1 3. 设是b的二进制表示 4. for i←k downto 0 5. do c ← 2c 6. d ← (d*d) mod n 7. if b[i] = 1 8. then c ← c + 1 9. d ← (d*a) mod n 10. return d 首先说明一下，上述伪代码中用缩紧表示语句之间的层次关系，例如第5~9行都是for循环体 内的语句，第8~9行都是then里面的语句。

4、这是我比较喜欢的一种表示方法 ；） 上述伪代码依次计算出的每个幂或者是前一个幂的两倍，或者比前一个幂大1。

5、过程依次从 右到左逐个读入b的二进制表示已控制执行哪一种操作。

6、循环中的每次迭代都用到了下面的 两个恒等式中的一个： a^(2c) mod n = (a^c mod n)^2 a^(2c+1) mod n = a * (a^c mod n)^2 用哪一个恒等式取决于b[i]=0还是1。

7、由于平方在每次迭代中起着关键作用，所以这种方法 叫做“反复平方法(repeated squaring)”。

8、在读入b[i]位并进行相应处理后，c的值与b的 二进制表示的前缀的值相同。

9、事实上，算法中并不真正需要变量c， 只是为了说明算法才设置了变量c：当c成倍增加时，算法保持条件d = a^c mod n 不变，直 至c=b。

10、 如果输入a,b,n是k位的数，则算法总共需要执行的算术运算次数为O(k)，总共需要执行的位 操作次数为O(k^3)。

11、

本文到此讲解完毕了，希望对大家有帮助。