Blog·Tanky WooABOUTRSS

快速幂取模

07 Sep 2010
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

Miller Rabbin测试素数这篇文章里的Modular_Exp函数里,就用到了快速幂取模的思想。 这里总结下。 求a^b%c(这就是著名的RSA公钥的加密方法) 当a,b很大时,直接求解这个问题不太可能 你能想到哪些优化呢? 算法1:直观上,也许最容易想到的是利用ab%c=((a%c)b)%c,这样每一步都进行这种处理,这就解决了a^b可能太大存不下的问题,但这个算法的时间复杂度依然是O(n),根本没有得到优化。当b很大时运行时间会很长 算法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^(p(i)2(i-1)))^2 利用这一点,我们可以递推地算出所有的a^(2^i) 当然由算法1的结论,我们加上取模运算a^(2^i)%c=((a^(2(i-1))%c)a^(2(i-1)))%c 于是再把所有满足p(i)=1的a^(2^i)%c按照算法1乘起来再%c就是结果 即二进制扫描从最高位一直扫描到最低位。


模板:

__int64 exp_mod(__int64 a, __int64 n, __int64 b)
{
    __int64 t;
    if(n==0) return 1%b;
    if(n==1) return a%b;
    t=exp_mod(a,n/2,b);
    t=t*t%b;
    if((n&1)==1) t=t*a%b;
    return t;
}

给大家一道题目强化一下: POJ 1995 Raising Modulo Numbers http://acm.pku.edu.cn/JudgeOnline/problem?id=1995

解答报告: http://www.wutianqi.com/?p=1263