快速幂取模

利用二进制扫描的方法快速的计算a^b mod c，显然用常规方法计算7⁴²³⁷mod 4233计算量过大。

基本原理：（a×b）mod c=((amod c)×b）mod c

例如：3⁵mod 7=3^(101)₂ mod 7=((3^(100)₂mod 7)×3）mod 7=((9^(10)₂mod 7)×3）mod 7=(((9mod 7)^(10)₂mod 7)×3）mod 7=((2^(10)₂mod 7)×3）mod 7=((4^(1)₂mod 7)×3）mod 7=(4×3）mod 7=5

实现代码如下（C语言版）

int exp_mod(int a,int b,int n){
	int r=1;
	while(b){
		if(b&1)r=(r*a)%n;
		a=(a*a)%n;
		b>>=1;		
	}
	return r;
}

时间复杂度分析：若a、b、n都是β位数，则所需算术运算的次数是O(β)，所需位操作总次数是O(β³)