首页 > 代码库 > 快速幂取模算法【模板】
快速幂取模算法【模板】
快速幂取模其实是a^b%c,这就是著名的RSA公钥加密的方法,当a,b都很大的时候,直接求是不可取的,所以就用到了快速幂取模。
首先你得明白他的原理,其实是用到了二分的思想,把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
【http://baike.baidu.com/view/1431260.htm】此处有详细的介绍。
这里给出非递归的方法:
long long modexp(long long a, long long b, int mod) { long long res=1; while(b>0) { //a=a%mod;(有时候n的值太大了会超出long long的储存,所以要先取余) if(b&1)//&位运算:判断二进制最后一位是0还是1,&的运算规则为前后都是1的时候才是1; res=res*a%mod; b=b>>1;//相当于除以2; a=a*a%mod; } return res; }
快速幂取模算法【模板】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。