快速幂取模

Miller Rabbin测试素数这篇文章里的Modular_Exp函数里,就用到了快速幂取模的思想。
这里总结下。
求a^b%c(这就是著名的RSA公钥的加密方法)
当a,b很大时,直接求解这个问题不太可能
你能想到哪些优化呢?
算法1:直观上,也许最容易想到的是利用a*b%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就是结果 即二进制扫描从最高位一直扫描到最低位。


模板:

1
2
3
4
5
6
7
8
9
10
__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

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《快速幂取模》有13个想法

  1. 我们要考虑的仅仅是p(i)=1的情况
    a^(2^i)=(a^(p(i)*2(i-1)))^2

    这句话有问题好像,第二行的2(i-1)))^2中,应该是2^(i-1)

  2. 很好, 很强大…… 豆豆你现在比我厉害好多了………….. [s:11] [s:11] [s:11]

    我这段时间都不知道在做什么了………….. [s:21]

发表评论

电子邮件地址不会被公开。 必填项已用*标注