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