Pollard Rho算法是一个非常玄学的算法(我个人还不是很懂其原理),作用是分解出一个数的非平凡因子(除1和它本身),通常作用于对大数的质因数分解.期望复杂度为O(n1/4).总体来说运行效果还是相当不错的.
算法核心:y=x,x=x*x+c.其中x,y初值是随机生成的,c也是随机生成的常数,假设算法求的是n的因子,最后要判断的是g=gcd(abs(y-x),n),如果g大于1,则找到了一个因子g,否则y和x继续按公式更新,重复操作.
不过y和x都是再模n的条件下生成的,因此这么生成下去是会产生环的,因此需要判环,也就是判y是否等于x.
整个代码可以用倍增优化,需要设z用来存储每次x更新后的abs(y-x)的积,然后有大佬指出每跑完127次之后有大概率能找到一个因子.
具体细节可以参考一下以下两篇文章,这里不多叙述(不是很懂).
1 LL p_rho(LL n) 2 { 3 while(1) //一定找到一个因子 4 { 5 LL x=rand()%n,y=x,c=rand()%n,z=1; 6 int i=1,j=1; 7 while(i++) 8 { 9 x=(q_muti(x,x,n)+c)%n; //q_muti为快速乘 10 z=q_muti(z,abs(y-x),n); 11 if(x==y||!z) break; 12 if(!(i%127)||i==j) 13 { 14 LL g=gcd(z,n); 15 if(g>1) return g; 16 if(i==j) y=x,j<<=1; 17 } 18 } 19 } 20 }
这里再给出完整的质因数分解模板需要同时用到Miller-Rabin素数测试和Pollard Rho算法
原文：https://www.cnblogs.com/VBEL/p/11426236.html