首页 > 代码库 > 大数质因解：浅谈Miller-Rabin和Pollard-Rho算法
大数质因解：浅谈Miller-Rabin和Pollard-Rho算法
2017-07-19 08:54 Amphetamine:能发一下代码吗？
应我那位谜一样好友的邀约，我打算好好看一看Miller-Rabin和Pollard-Rho算法。很奇怪，各种地方有很多代码描述详细过程，但我仍旧很懵。也许是我太弱了，不能从那些“鱼龙混杂”的代码中找出本质上的共性。那么，我们现在来讨论一下吧。
首先，大整数分解现在仍然是个世界级的难题，在“公共密钥”的研究上有着重要的作用。
！！先判断质数！！
试除法：原始的根号算法
额。不想说了。正经一点。
Miller-Rabin：判断一个“p”是否是质数
首先，快速幂是极为必要的。
YYR说，这种东西是要靠RP的。但是，99.999%应该还是足以解决一些问题（或是大多数）了。
a^(p-1)≡1(mod p)，gcd(a,p)=1
费马小定理是极强的质数性质。只要找到一个a，与那个“p”不满足上述条件，就可以跳合数了？答案是肯定的。
但是，如果找不到呢？就是质数？呵呵，很可惜啊。因为存在Carmichael数：无论取多少个a，有一个不满足，算我输。
比如：561 = 11*51就是一个Carmichael数。
为了99.999%，YYR给了一种相对靠谱的方法。
【PART 1：必要的第一次粗筛】
先把2,3,5,7,11,13拿来筛一遍。
这样理论上可以筛掉：1-(1-1/2)*(1-1/3)*(1-1/5)*(1-1/7)*(1-1/11)*(1-1/13)=1-19.18%=80.82%的数。
当然，如果再加上17,19,23,29，理论上可以只会留下15.79%的数，也就是筛去了84.21%的数。
肯定，我们会发现，这个筛率会趋于收敛。
但是，让我们专门卡素数，怎么可能只用这种方法！！！
【PART 2：费马小定理与“二次探测定理”】
在进入这一步之前，我们还不能确定这个“p”的身份。
我们此时会先把p-1搞一搞，不停地除以2。直到发现p-1=2^k*t，而t是奇数。
这样有何用意？且让我们分析。有一个定理：
若a^2≡1(mod p)，则a≡±1(mod p)
YYR说到这里时，我说这很显然，他瞪大了眼睛。因为若p|(a^2-1)，就有p|(a+1)(a-1)。这是经典的欧几里得引理，他以此证明了唯一分解定理。我们有(a+1)%p==0或(a-1)%p==0。即a≡±1(mod p)。
然后，我们可以去随机地选取一些a。首先用快速幂算出a^t%p，然后把这个数自乘。得到了a^2t%p，然后再自乘。得到了a^4t%p，然后再自乘……我们可以发现，a^t%p自乘k次以后，就可以得到a^(2^k*t)%p，最后就是a^(p-1)%p了。
在这样的一条路上，我们可以充分验证上述“定理”。前面k-1个数中只要出现了1，而它的“父亲”（它的“父亲”自乘得到了它）不是±1，那么就可以跳合数了。最后，第k个数即a^(p-1)%p若不为1，也可以跳合数。
为什么这样效率很高？事实证明，若“p”通过一次测试，不是素数的概率为25%。若“p”通过x次测试，则不是素数的概率为1/(4^x)。当x=5时，素数误判的概率为1/(4^5)=1/1024=0.10%，已经直逼99.90%了。
而假如选取了4个a为2,3,5,7，则在2.5*10^13以内唯一一个失误的数为3215031751。
所以说，选几个a比较好？实践证明，这种东西可以悠着来。
【小结】
1.读入一个"p"。
2.用2,3,5,7,11,13粗筛，发现整除直接跳合数。
3.把p-1搞一搞，不停地除以2。得到奇数t，和一个数k。p-1=2^k*t。
4.随机地找一个数a，算出x=a^t。
5.last=x,x=x*x%p,若x==1且last!=1且last!=p-1，则跳合数。该步骤重复k次。
6.现在x=p-1，若x!=1，则跳合数。
7.按心情回到第4步，99.99%与99.9999%在神犇眼里有着本质区别。
！！然后再乱搞！！
FERMAT：平方差
如果是偶数，就把它釜底抽薪，变成奇数。
对于一个奇数N，若不为质数，则设N=c*d，明显c、d均为奇数。
不妨设c>d，令a=(c+d)/2,b=(c-d)/2，很明显，N=a*a-b*b。这就是了。
我们枚举一个a，有a*a-N=b*b，a>=sqrt(N),若a*a-N是一个完全平方数，就可以递归了。
但是，很明显。这样也是枚举，效率很低，得不偿失。
单纯的POLLARD RHO：生日悖论和判圈
-----------------------------------------未完待续------------------------------------------
大数质因解：浅谈Miller-Rabin和Pollard-Rho算法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。