1. Pollard Rho 的生日悖论基础中为什么随机采样能在 O(n^{1/4}) 期望时间内找到因子？
问题
Pollard Rho 算法如何基于生日悖论，在 O(n^{1/4}) 期望时间内找到合数 n 的一个因子？
考察点
- 生日悖论与碰撞
- Pollard Rho 的随机游走
- O(n^{1/4}) 复杂度推导
答案
设 n 有一个小因子 p。若在模 p 下随机采样元素，由生日悖论，约 O(√p) 个样本后就出现两个相等的值（碰撞），即 x_i ≡ x_j (mod p)。此时 p | (x_i - x_j)，所以 gcd(x_i - x_j, n) 含有因子 p（可能为 p 或 n 的更大因子）。Pollard Rho 用伪随机函数 f(x)=x^2+c 生成序列并检测碰撞，不用真的随机采样。由于 p 是 n 的最小素因子，p ≤ √n，故期望步数 O(√p) ≤ O(n^{1/4})。每次碰撞检测用 gcd 验证，最终剥离出非平凡因子。
解析
关键洞察是"在模 p 下的碰撞"而非"模 n 下的碰撞"，因为因子 p 是小范围，碰撞更容易出现。生日悖论把寻找因子的期望从 O(p) 降到 O(√p)，从而整体 O(n^{1/4})。
示例代码
long pollardRho(long n) {
if (n % 2 == 0) return 2;
long c = 1, x = 2, y = 2, d = 1;
while (d == 1) {
x = (mulMod(x, x, n) + c + n) % n;
y = (mulMod(y, y, n) + c + n) % n;
y = (mulMod(y, y, n) + c + n) % n; // Floyd 快慢指针
d = gcd(Math.abs(x - y), n);
}
return d == n ? pollardRho(n) : d; // 失败换 c 重试
}