关于Floyd判环、Brent判环和分组gcd的优化

对于Pollard Rho算法的判环，最开始Pollard在1974年的算法使用的是Floyd判环，后来Brent在1980年提出了Brent判环，对Floyd判环做了常数上的改进。两个算法关于rho的长度都是线性的，但是Brent的判环执行函数迭代的次数比Floyd的少，且使得Pollard Rho算法的平均运行时间减少了24%。

同时，Pollard在算法提出第二年，即1975年的论文里注意到原算法中调用了过多的gcd函数，他提出可以跑大概 $m=100$ 次迭代再运行一次gcd，这样可以显著提高运行速度。直觉上，这样使得算法复杂度从 $O(N^{1/4}\log N)$ 降低到了 $O(N^{1/4}+(N^{1/4}/m)\log N)$ （但是牺牲了部分判断的准确度，所以严谨分析很困难）。

Brent判环和分组gcd优化是两个独立的优化，很多题解以及oi-wiki都将它们混淆，可能会造成困惑。这里简单梳理一下，希望能帮助到同样困惑的同学。