首页 > 代码库 > 快速幂取模算法【模板】

快速幂取模算法【模板】

快速幂取模其实是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;
}




快速幂取模算法【模板】