Pollard's Rho（大数因数分解）

数学与数论 · 生日悖论 · 让因子自己显影

试除的墙

分解 n 最朴素的办法是拿 2, 3, 5, … 一路试除到 √n——n 有几百位时这堵墙高到天上。Pollard's Rho 换了个哲学：不去挨个「找」因子，而是造一串伪随机数（x ← x² + 1 mod n），让 n 里藏着的因子 p 在生日悖论的巧合中自己现形。

两个世界与 gcd 显影

关键的想象力：这串数同时活在两个世界里。在 mod n 的世界（你能看见的）它乱跳；在 mod p 的世界（p 是未知因子、你看不见）它也在游走——但那个世界只有 p 个位置，生日悖论说约 √p 步就会撞车、进入循环，轨迹画出来是个 ρ 字形（尾巴 + 环——算法名字的由来）。撞车意味着两个数 x ≡ y (mod p) 而 x ≠ y (mod n)——它们的差是 p 的倍数但不是 n 的倍数，于是：

gcd(|x − y|, n) 就是显影液——把看不见的 p 冲洗出来。
怎么高效制造「撞车对」？Floyd 龟兔：乌龟每次走 1 步、兔子走 2 步，兔子在环上必追上乌龟；每走一步做一次 gcd，命中即得因子。期望 O(n^¼)（p ≤ √n，撞车要 √p 步）。

下图分解 n = 8051：节点是序列值、箭头是 x → x²+1 的走向，蓝环是龟兔当前位置；最后一步揭开 mod 97 的世界——同色节点即「同一站台」，ρ 字形一目了然。

分解 n = 8051。试除法要拿 2, 3, 5, … 一路除到 √n ≈ 90（24 个素数逐个试）；数再大一点（比如 RSA 的几百位）试除直接判死刑。Pollard's Rho 换思路：不去「找」因子，让因子自己在随机序列里「显影」

1function pollardRho(n: bigint): bigint {
if (n % 2n === 0n) return 2n;
const f = (x: bigint): bigint => (x * x + 1n) % n;   // 伪随机步进
let slow = 2n;
let fast = 2n;
let d = 1n;
while (d === 1n) {
  slow = f(slow);                       // 龟：1 步
  fast = f(f(fast));                    // 兔：2 步
  d = gcd(slow > fast ? slow - fast : fast - slow, n);  // 显影
}
return d === n ? retryWithNewC(n) : d;  // 命中因子（撞满环则换 c 重来）
13}
14// 判素交给米勒-拉宾；合数用 Rho 劈半后递归，即得完整分解

n8051（其实 = 83 × 97，装作不知道）

目标找出一个非平凡因子

1 / 7

完整的分解流水线

Rho 只负责「劈一刀」：拿到因子后两半各自递归。判断「还要不要劈」交给米勒-拉宾——先判素、合数才进 Rho，配合快速幂与 gcd，一条大数分解流水线就齐了。工程上常用 Brent 变体（批量累乘差值、gcd 次数减半）；反过来看，RSA 敢公开 2048 位的 n，正是笃定 n^¼ ≈ 2⁵¹² 这个量级谁也啃不动——判素易、分解难这对不对称，就是现代密码学的地基。至此数论大类十页收官：从筛法数素数、CRT 拆同余，到判素与分解，一条线走完。

算法可视化

Pollard's Rho（大数因数分解）

试除的墙

两个世界与 gcd 显影

完整的分解流水线