Pollard-rho算法详解

Pollard'sRho|BIGBALLON1AQuickTutorialonPollard'sRhoAlgorithm在研究pollardrho算法的时候，无意间看到的这篇文章，觉得写得很好，就将其翻译为中文，可能有些地方翻译地不是很好。原文链接，请点这里目录AQuickTutorialonPollard'sRhoAlgorithm.............................................................................................1历史...................................................................1问题的设置.............................................................2通过𝐁𝐢𝐫𝐭𝐡𝐝𝐚𝐲𝐓𝐫𝐢𝐜𝐤提高概率............................................3利用生日悖论来因数分解.................................................6Pollard'sRho算法.....................................................7历史Pollard’sRho算法是一个非常有趣又容易理解的整数因子分解算法。它并不是目前最快的算法，但它要比试除法快上多个量级。它基于非常简单的思想，而这种思想同样可以用于其他地方。这个算法最早出自JohnM.Pollard在1975年所写的论文Pollard,J.M.(1975),“AMonteCarlomethodforfactorization”,BITNumericalMathematics15(3):331–334紧接着在1980年RichardBrent在他的论文中提出了一些改进Brent,RichardP.(1980),“AnImprovedMonteCarloFactorizationAlgorithm”,BIT20:176–184,doi:10.1007/BF01933190更多的内容，可以查看维基百科Pollard'srhoalgorithmPollard'sRho|BIGBALLON2问题的设置我们假设𝑵是一个能被分解为𝒑∗𝒒的数(𝑵=𝒑∗𝒒且𝒑≠𝒒)我们的目标是找到𝑵的其中一个因子𝒑或𝒒(另外一个因子可以通过除𝑁来得到)我们先来看传统的试除法intmain(){intN,i;//ReadinthenumberNscanf(%d,&N);printf(YouenteredN=%d\n,N);if(N%2==0){puts(2isafactor);exit(1);}for(i=3;iN;i+=2){if(N%i==0){printf(%disafactor\n,i);exit(1);}}printf(Nofactorfound.\n);return1;}让我们用一个更暴力的版本：Iamfeelingluckyalgorithm（注意，下面的代码并不是完美的）intmain(intargc,char*constargv[]){intN,i;//ReadinthenumberNscanf(%d,&N);printf(YouenteredN=%d\n,N);i=2+rand();//Getsanumberfrom0toRAND_MAXif(N%i==0){printf(Ifound%d\n,i);exit(1);}printf(gofishing!\n);}Pollard'sRho|BIGBALLON3Iamfeelingluckyalgorithm将会生成一个[2,𝑁]的随机数，然后检查是否找到了某个因子。那么找到因子的概率是多少呢？答案非常简单：在这𝑁−1个数中，我们恰好只有两个因子𝑝和𝑞。因此概率就是2𝑁−1,如果𝑁~1010，那么成功的机会约为𝟏𝟓𝟎𝟎𝟎𝟎𝟎𝟎𝟎𝟎𝟎,这比购买一张彩票中奖的概率还要小，换句话说，我们不得不使用不同的随机数重复将近𝑁次来找到一个因子，显然，这比试除法还要糟糕。通过𝐁𝐢𝐫𝐭𝐡𝐝𝐚𝐲𝐓𝐫𝐢𝐜𝐤提高概率这是一个简单而又十分有用的提高概率的技巧，它被叫做BirthdayTrick。我们举例来说明这个trick。从[1,1000]中随机取一个数，取得42的概率为11000，事实上，取得任意一个数的概率均为11000。我们稍微修改一下这个问题：从[1,1000]中随机选取两个数𝑖和𝑗，𝑖−𝑗=42(𝑖≠𝑗)的概率是多少？能够粗略地算出，此时的概率大约为1500。如果我们不再坚持仅选取1个数并且这个数必须为42，而是能够选取2个数并且他们的差刚好等于42，那么，成功的概率被提高了。如果我们在[1,1000]中选取𝑘个数𝑥1,……,𝑥𝑘，取得的𝑘个数中满足𝑥𝑖−𝑥𝑗=42的概率是多少呢？这个概率和𝑘有什么关系呢？答案的计算并不是很困难，但是我们还是编写一个简单的程序来实际验证一下#includestdio.h#includestdlib.hintmain(intargc,int*argv){inti,j,k,success;intnTrials=100000,nSucc=0,l;int*p;/*Readinthenumberk*/Pollard'sRho|BIGBALLON4printf(Enterk:);scanf(%d,&k);printf(\nYouenteredk=%d\n,k);if(k2){printf(selectak=2please.\n);return1;}/*Allocatememoryforourpurposes*/p=(int*)malloc(k*sizeof(int));//nTrials=numberoftimestorepeattheexperiment.for(j=0;jnTrials;++j){success=0;//Eachexperimentwillgeneratekrandomvariables//andcheckifthedifferencebetween//anytwoofthegeneratedvariablesisexactly42.//Theloopbelowfoldsbothin.for(i=0;ik;++i){//Generatetherandomnumbersbetween1and1000p[i]=1+(int)(1000.0*(double)rand()/(double)RAND_MAX);//Checkifadifferenceof42hasbeenachievedalreadyfor(l=0;li;++l)if(p[l]-p[i]==42||p[i]-p[l]==42){success=1;//Success:wefoundadiffof42break;}}if(success==1){//Wetrackthenumberofsuccessessofar.nSucc++;}}//Probabilityissimplyestimatedbynumberofsuccess/numberoftrials.printf(Est.probabilityis%f\n,(double)nSucc/(double)nTrials);//Donotforgettocleanupthememory.free(p);return1;}Pollard'sRho|BIGBALLON5你可以使用不同的𝑘(𝑘≥2)值来运行上面的代码KProb.Est.20.001830.005440.0112350.01860.0284100.08196150.18205200.30648250.4376300.5661000.9999这张表格展示了概率奇妙的分布情况。大约在𝑘=30的时候，成功的概率已经超过一半。我们有一个大区间[1,1000]，但是仅仅生成约30个随机数就让我们成功的概率超过了一半，大约在𝑘=100的时候，我们几乎可以确保我们是成功的。这是一个非常重要的观察，它被成为生日问题(𝑏𝑖𝑟𝑡ℎ𝑑𝑎𝑦𝑝𝑟𝑜𝑏𝑙𝑒𝑚)或者生日悖论(𝑏𝑖𝑟𝑡ℎ𝑑𝑎𝑦𝑝𝑎𝑟𝑎𝑑𝑜𝑥)我们随机选择一名学生，他的生日为4月1日的概率为1365这相当于我们在[1,365]中随机选取一个数，该数为90的概率是多少？那么我们又回到了上面那个问题。我们随机选取𝑘(𝑘≥2)个人，他们的生日相同的概率是多少？我们只需要将代码中的差值42进行修改即可#includestdio.h#includestdlib.hintmain(intargc,int*argv){inti,j,k,success;intnTrials=100000,nSucc=0,l;int*p;printf(Enterk:);scanf(%d,&k);printf(\nYouenteredk=%d\n,k);p=(int*)malloc(k*sizeof(int));//Wewilldo1000repsfor(j=0;jnTrials;++j){Pollard'sRho|BIGBALLON6success=0;for(i=0;ik;++i){//Generatetherandomnumbersbetween1and365p[i]=1+(int)(365*(double)rand()/(double)RAND_MAX);//Checkifadifferenceof42hasbeenachievedfor(l=0;li;++l)if(p[l]-p[i]==0){success=1;break;}}if(success==1){nSucc++;}}printf(Est.probabilityis%f\n,(double)nSucc/(double)nTrials);return1;}我们可以看到，k=10的时候大概有11%的可能性存在两个人生日相同的情况，而k=23时，可能性提高至50%，我们的班级总共有58个人，而𝑘=58时的可能性已达到99%，几乎可以肯定地说，一个班级里必定有两个同学的出生日期是相同的，而这么多年的求学生涯过来了，这个概率“似乎”是不正确的，这便是悖论了。(这里我们把k≥366作为数学上精确的100%)如果一年中有𝑁天(在我们的星球上𝑁=365)，那么每𝑘=√𝑁个人中有50%的可能性产生生日冲突。利用生日悖论来因数分解让我们回到Iamfeelingluckyalgorithm。我们随即地从[1,N]中选择一个数，这个数是p或者q的可能性是非常小的，所有我们不得不重复运行算法来提高概率。那么，我们现在可以提出一个不同的问题：不再只选取一个整数，我们能够选取𝑘个数，并问是否存在𝑥𝑖−𝑥𝑗能够整除𝑁我们已经知道对于𝑘=√𝑁,我们可以将可能性提高到50%，所以，可以粗略地说，我们可以将可能性从1𝑁提高到√1𝑁。Pollard'sRho|BIGBALLON7因此，对于一个10位的整数，我们只需要选取𝑘=105个随机数而不是1010个。不幸的是，这没有节省我们的开销，对于𝑘(𝑘=105)个人来说，我们仍然要做𝑘2=1010次比较和除法。但幸运的是，这里有一个更好的办法。我们可以选取𝑘个数𝑥1,……,𝑥𝑘，不再问是否存在𝑥𝑖−𝑥𝑗能够整除𝑁，转而询问是否存在𝑔𝑐𝑑(𝑥𝑖−𝑥𝑦,𝑁)1的情况。换句话说，我们问𝑥𝑖−𝑥𝑦和𝑁是否存在一个给平凡的最大公约数如果我们问有多少个数能整除𝑁，答案只有两个，𝑝和𝑞如果我们问有多少个数使得𝑔