对于Pollard Rho算法的判环,最开始Pollard在1974年的算法使用的是Floyd判环,后来Brent在1980年提出了Brent判环,对Floyd判环做了常数上的改进。两个算法关于rho的长度都是线性的,但是Brent的判环执行函数迭代的次数比Floyd的少,且使得Pollard Rho算法的平均运行时间减少了24%。
同时,Pollard在算法提出第二年,即1975年的论文里注意到原算法中调用了过多的gcd函数,他提出可以跑大概 m=100 次迭代再运行一次gcd,这样可以显著提高运行速度。直觉上,这样使得算法复杂度从 O(N1/4logN) 降低到了 O(N1/4+(N1/4/m)logN) (但是牺牲了部分判断的准确度,所以严谨分析很困难)。
Brent判环和分组gcd优化是两个独立的优化,很多题解以及oi-wiki都将它们混淆,可能会造成困惑。这里简单梳理一下,希望能帮助到同样困惑的同学。