快速幂取模

利用二进制扫描的方法快速的计算a^bmod 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(β³)