\(f(x)=x^2+c\) 满足:\(\forall x \equiv y\pmod n\),\(f(x)\equiv f(y) \pmod n\).
用 \(f(x)\) 生成一列数 \(a_0 = x, a_n = f^{(n)}(x)=f(a_{n-1})\).
这意味着对要分解的数 \(m\) 的一个因子 \(p\),\(\{a_n \bmod p\}\) 的循环节不超过 \(p\),即我们可以期望在 \(p\) 次内通过 \(\gcd(a_i-a_j, m)\) 分解出 \(p\),其中 \(\left| i-j \right|\) 每次增加 \(1\).
如果用 rand(),则没有这样的性质.
标签:pmod,生成,pollard,算法,rho,equiv From: https://www.cnblogs.com/x383494/p/17069031.html