模幂运算 a^b%c

2019-04-14 14:41发布

站内文章 / 模拟电子
16478 0 1749
1）模幂运算1—累次计算法：
d＝ ar mod m
 ＝(…((((a mod m)*a) mod m)*a)mod m…*a)mod m  
算法 long modular_power1(long a, long r, long m){ long d=1, k; a=a % m; for(k=0；k


（2）模幂运算2—快速计算法
  将r化为二进制数的形式( bkbk-1…b2b1b0)，然后反复平方取余数。然后从最低位开始，自右至左逐位扫描。每次迭代时．用到下面两个恒等式中的；
a^2c mod m=(a^2)^c mod m a^(2c+1) mod m=a*(a^2)^c mod m





模取幂运算—快速计算实现
long modular_power1(long a, long r,long m){ long d,t; d=1;t=a; while (r>0){ if ((r%2)==1) d=(d*t) % m; r=r/2; t=t*t % m; } return d; }

热门文章