快速幂取模算法

快速幂取模算法

快速幂取模 是一种常用的算法，这里总结下。 求a^b%c（这就是著名的RSA公钥的加密方法），当a,b很大时，直接求解这个问题不太可能  算法1：利用公式a*b%c=((a%c)*b)%c,这样每一步都进行这种处理，这就解决了a^b可能太大存不下的问题，但这个算法的时间复杂度依然没有得到优化 代码如下：

int Mod1(int a,int b,int n) { int cnt = 1; while (b--) { cnt = a * cnt % n; } return cnt;}

算法2：另一种算法利用了二分的思想，可以达到O(logn)。

可以把b按二进制展开为：b = p(n)*2^n  +  p(n-1)*2^(n-1)  +…+   p(1)*2  +  p(0)

其中p(i) (0<=i<=n)为 0 或 1

这样 a^b =  a^ (p(n)*2^n  +  p(n-1)*2^(n-1)  +...+  p(1)*2  +  p(0))

=  a^(p(n)*2^n)  *  a^(p(n-1)*2^(n-1))  *...*  a^(p(1)*2)  *  a^p(0)

对于p(i)=0的情况, a^（p(i) * 2^(i-1) ） =  a^0  =  1,不用处理

我们要考虑的仅仅是p(i)=1的情况

化简：a^(2^i)  = a^(2^(i-1)  * 2) = (  a^(  p(i)  *  2^(i-1)  )  )^2

（这里很重要！！具体请参阅秦九韶算法：​​a^(2^i)%c = ( (a^(2^(i-1))%c) * a^(2^(i-1)))  %c于是再把所有满足p(i)=1的a^(2^i)%c按照算法1乘起来再%c就是结果， 即二进制扫描从最高位一直扫描到最低位

实例代码：递归

int Mod2(int a,int b,int n){ int t = 1; if(b == 0) return 1; if(b == 1) return a%n; t=Mod2(a, b>>1, n); t=t*t%n; if (b&1) { t = t*a % n; } return t;}

实例代码2：非递归优化 :

int Mod3(int a,int b,int y){ int cnt=1; while(b) { if(b&1) cnt=cnt*a%y; a=a*a%y; b>>=1; } return cnt;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。