企业官网建设流程全解析

Pollard-ρ 因子分解算法

算法：Pollard’s Rho Algorithm（Pollard-ρ 因子分解）
来源：TAOCP 第2卷 第4.5.4节
文件：pollard_rho.c

5W1H

Who（谁提出）

John M. Pollard，1975年在论文“A Monte Carlo method for factorization”中提出。他同年还提出了 Pollard p-1 算法，是数论算法的重要贡献者。Floyd 判圈算法由 Robert W. Floyd 独立发现（约1967年）。

What（是什么）

Pollard-ρ 是一种概率性整数因子分解算法：

1. 选迭代函数f(x) = (x² + c) mod n
2. 用 Floyd 判圈法（龟兔赛跑）检测序列中的周期
3. 当gcd(|tortoise - hare|, n)落在(1, n)时，找到非平凡因子

名称来自算法轨迹在模图中呈现的 ρ（rho）字形：一段尾巴连接一个环。

When（何时使用）

• 分解中等大小的整数（10⁶ 到 10¹²）
• 密码学分析（RSA 小因子攻击）
• 需要比试除法更快但不需要 GNFS 级别复杂度时

时间复杂度：O(n^(1/4))期望步数，远优于试除法的 O(n^(1/2))。

Where（在哪里重要）

TAOCP 4.5.4节"因子分解方法"中详细分析了该算法，并将其与 Lehman 方法、二次筛法进行比较。在密码学历史上，Pollard-ρ 是第一个实用的亚线性因子分解算法，推动了 RSA 密钥长度标准的提升。

Why（为什么有效）

基于生日悖论：在一个 p 个元素的集合中随机取值，约 O(√p) 步后就会出现碰撞。由于 n 的最小质因子 p 满足 p ≤ √n，算法期望在 O(p^(1/2)) ≈ O(n^(1/4)) 步内找到 p。

How（如何实现）

Floyd 判圈（龟兔赛跑）：

tortoise = f(tortoise) // 走1步 hare = f(f(hare)) // 走2步 d = gcd(|tortoise - hare|, n) 若 1 < d < n：找到因子 d 若 d == n：退化，换 c 重试

mulmod 防溢出：

// 使用 __int128 避免 a*b 超出 long long 范围staticllmulmod(ll a,ll b,ll m){return(ll)((__int128)a*b%m);}

需求定义

功能需求

1. mulmod(a, b, m)— 安全模乘，使用__int128防溢出
2. gcd(a, b)— 迭代欧几里得算法
3. is_prime(n)— 试除法判素数（n < 10⁶ 范围高效）
4. pollard_rho(n, c)— 返回 n 的一个非平凡因子，失败返回 n
5. factorize(n, factors[], *nfactors)— 完全质因子分解
6. factorize_helper— 递归分解（内部）

非功能需求

• 所有计算使用long long（64位），乘法使用__int128
• 不使用 math.h，不链接 -lm
• 编译无警告：gcc -std=c99 -Wall
• 处理范围：n < 10⁹（测试范围），理论上支持到约 10¹⁵

约束

• pollard_rho最多迭代 1,000,000 步（防止死循环）
• factorize_helper尝试 c=1 到 c=19，若全部失败则退化处理
• 因子列表最大 64 个（对于 n < 10¹⁵ 远够用）

验收标准

算法复杂度对比

Pollard-ρ 是实用性与实现简单性的最佳平衡点。

历史意义

1994年，Peter Shor 提出量子因子分解算法（Shor算法），理论上能在多项式时间内分解任意整数，使 RSA 面临量子威胁。然而在量子计算机真正实用化之前，Pollard-ρ 仍是经典计算机上最重要的实用因子分解工具之一。

生成日期：2026-03-22
系列：The Art of Computer Programming 实现集