快速幂是什么？

解释一下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<t+1
因为 b是个整数 所以
t=log(2)b
时间复杂度比直接循环求a^b大大的降低了

模取幂运算

事实上，m^e mod n可以直接计算，没有必要先算m^e。
m^e mod n叫做模取幂运算，根据简单的数论知识，很容易设计一个分治算法。具体如下:

设<b[k], b[k-1],...,b[1],b[0]>是整数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[k],b[k-1],..b[0]>是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里面的语句。这是我比较喜欢的一种表示方法 ；）

上述伪代码依次计算出的每个幂或者是前一个幂的两倍，或者比前一个幂大1。过程依次从