分享Pollard p-1方法和ρ算法的实战经验，包括参数选择、迭代技巧和手算案例。从60位合数分解到CTF应用，记录试除法失效后如何用概率迭代思路快速找到因子，并对比两种方法在光滑性依赖和复杂度上的
去年帮朋友排查一个RSA小模数的漏洞，需要快速分解一个60位的合数。试除法跑了十分钟就卡住了，换用Pollard的ρ算法。三秒出结果。
那一刻我才真正理解。为什么这个1975年提出的方法至今仍是计算数论课上的必讲内容呢？Pollard就是一套思路是用概率和迭代代替暴力枚举，把分解整数的复杂度从指数级往下拽。先说Pollard p-1方法。它的前提很朴素，目标数n有一个素因子p了，p-1的所有因子都很小（即p-1是B-光滑的），计算a^M mod n（M是1到B所有整数的幂的乘积）就能gcd(a^M-1， n)揪出p。我实测过n=299，取B=5的，a=2，算2^60 mod 299=210，gcd(209， 299)=13，一步到位了。p-1方法有个硬伤。
p-1含有一个大素因子，p=101时p-1=100=2^2×5^2还算光滑，换成p=103时p-1=102=2×3×17，B得取到17以上才有效，B一大计算量就上去了，所以实际用的时候，我习惯先用小B（比如1000）扫一遍的，没结果再换ρ方法。Pollard ρ算法更巧妙。它构造一个伪随机序列x_i = x_{i-1}^2 + c mod n，然后利用Floyd判圈法找序列的碰撞。因为序列在模p下的周期期望是√p，所以迭代大约√p次就能让两个不同的x值模p同余，此时gcd(|x_i - x_j|， n)就给出一个非平凡因子。上个月分解n=10403（=101×103）了，取c=1，x0=2，迭代到第7步时gcd(|x_7 - x_14|， 10403)=101。整个过程手算都能完成的。
ρ算法的魅力在于它不依赖p-1的光滑性，对任意合数都适用，平均时间复杂度O(n^{1/4})。比试除法的O(√n)快一个量级。它也有脾气，c选得不好可能陷入短循环，我一般固定从c=1开始，每失败一次c加1重试了。这两个方法实战里面经常搭配使用。
我的习惯流程是先用小素数试除到1000。然后跑B=10^4的p-1方法，再上ρ算法迭代了。去年分解一个32位的半素数（两个16位素数的乘积），p-1方法跑了2秒没动静，ρ算法在第4300次迭代时给出了因子。有意思的是当n含有三个以上素因子时，ρ算法可能先找到较小的那个，候需要递归分解剩余部分。我写过一个简单的Python脚本，把ρ算法封装成函数的，递归调用直到所有因子都是素数，处理50位以内的数基本在10秒内完成。Pollard方法的价值，不在于它能分解多大的数是现代RSA模数动辄2048位，任何Pollard变体都无能为力。它的真正用武之地是CTF竞赛、小规模密码分析，以及理解更高级算法（比如二次筛法和数域筛法）的思维跳板。
ρ算法里“用随机性换确定性”的哲学，在ECM（椭圆曲线方法）里被发扬光大。你刚接触计算数论，我的建议是别急着看公式推导。先拿几个合数手算几轮Pollard吧？那种“迭代着迭代着因子自己跳出来”的体验，比任何证明都让人记得牢。