Pollard-Rho 算法
推导
对于一个已知的合数 \(n>3\)，我们的目标是快速找到它的一个非平凡因子（除 \(1\) 和 \(n\) 外）。
显然问题可以转化为找到一个 \(k\) 使得 \(1 \lt \gcd(k,n) \lt n\)。
考虑一个序列 \(f\)，满足 \(f_0=0\) 且 \(f_i = (f_{i-1}^2 + c) \bmod n\)，其中 \(c\) 是常数。由生日悖论1得 \(f\) 中不同的数量的期望为 \(O(\sqrt n)\)。
设 \(m\) 是 \(n\) 的最小质因子，显然有 \(m \le \sqrt n\)。
设 \(g_i = f_i \bmod m\)，则 \(g\) 中不同的数量的期望为 \(O(\sqrt m)\)。
于是我们可以在期望 \(O(\sqrt m) \le O(n ^ {\frac 1 4})\) 的时间内找到两个位置 \(i,j\) 使得 \(f_i \not = f_j \land g_i = g_j\)，即 \(n \nmid (f_i - f_j) \land m \mid (f_i - f_j)\)，于是有 \(1 \lt m \le \gcd(|f_i - f_j|, n) \lt n\)
于是我们可以在期望 \(O(n ^ {\frac 1 4})\) 的时间内找到 \(k\) 满足 \(1 \lt gcd(k,n) \lt n\)，也就找到了一个 \(n\) 的非平凡因子。