数论-反复平方法快速求幂取模运算

2019-04-13 13:59发布

站内文章 / 模拟电子
10709 0 1793
a^b mod n 当a^b的值超出整数范围时，mod运算便无法进行。为解决这个问题，引入“反复平方法”由公式a*b mod n =(a mod n)*(b mod n)modn=((a mod n)*b)mod nd=a^b mod n =(...((((a mod n)*a)mod n)*a)mod  n...*a)mod n 共b个a得到一个迭代式d=a;for i=2 to b do    d=d mod n * a;d=d mod n;时间复杂度为O(b),当b很大时，效率较低使用下面的公式a^2c mod n=(a^c)^2 mod na^(2c+1) mod n =a*(a^c)^2 mod n时间复杂度为O(logb)int fun(int a, int b,int n){int d=1,t=a;while(b>0){if(b%2==1) d=d*t %n;//b为奇数时b=b/2;t=t*t%n;}return d;}

热门文章