关于模取幂运算a^b mod n的问题--解析

              模取幂运算 计算a^b mod c
    利用公式: (a*b)mod(c) = ((a mod c )*b)mod c
算法思路：将幂模运算转化为乘模运算。

例：求D=C^15 % N，由于：a*b % n = (a % n)*(b % n) % n，所以：
C1 =C*C % N =C^2 % N
C2 =C1*C % N =C^3 % N
C3 =C2*C2 % N =C^6 % N
C4 =C3*C % N =C^7 % N
C5 =C4*C4 % N =C^14 % N
C6 =C5*C % N =C^15 % N

即：对于b=15的幂模运算可分解为6 个乘模运算，归纳分析以上方法可以发现
对于任意b，都可采用以下算法计算D=a^b % c：

 while(b>0)
 {
 if(b%2==0)
 { result=(result*result)%c;          // result初始值为1
 b=b/2;
 }
 else
 { result=(result*a)%c;
 b=b-1;                              
 }
 }

继续分析会发现,要知道E何时能整除 2，并不需要反复进行减一或除二的操作，只需验证E 的二进制各位是0 还是1 就可以，所以：

while(b)              //求b的二进制，存放在数组int x[]中
 {
  x[i++]=b%2;           
  b=b>>1;         //向右移位，此句也可改为b=b/2,意思一样哦
 }
 for(j=i-1;j>=0;j--)    
 { 
  result=(result*result)%c;        // result初始值为1
  if(x[j]==1)
  {
   result=(result*a)%c;
  }
 }

这样就可以实现a^b mod c的问题问题的解决了！

小建议：要是没办法理解全部，就记住这个性质，会用也就行了！