大数分解

大数分解把合数写成素数的乘积。它在公钥密码中居于核心地位：RSA 的安全性建立在"分解 $n=pq$ 在经典计算机上困难"这一经验事实上，而素性检验只能判定是否合数、不能给出因子。

试除法与 Pollard ρ

试除法到 $\sqrt n$ 是基准。Pollard ρ 算法（1975）用伪随机迭代找因子：取 $x_{i+1}=f(x_i)\bmod n$（如 $f(x)=x^2+1$），用 Floyd 判圈同时迭代 $x$ 与 $y=f(f(y))$，逐对计算 $d=\gcd(|x-y|,n)$；一旦 $d$ 落在 $(1,n)$ 之间即得非平凡因子。

Pollard p−1

若 $n$ 有素因子 $p$ 使 $p-1$ 只含小素因子（$B$-光滑），取 $M=\operatorname{lcm}(1,2,\dots,B)$，则 $a^M\equiv1\pmod p$，于是 $\gcd(a^M-1,n)$ 含有因子 $p$。适用于 $p-1$ 光滑的整数。

椭圆曲线分解法（ECM）

椭圆曲线上的标量乘法取代 Pollard p−1 中的幂：若 $\#E(\mathbb{F}_p)$ 光滑，倍数点在模 $p$ 下成为单位元，$\gcd$ 运算泄出因子 $p$。对中等大小因子（约 20–50 位）最优，且不要求 $p-1$ 光滑。

数域筛法（NFS）

当前对大整数最快的通用算法，亚指数复杂度

$$L_n[1/3,\,c]=\exp\bigl((c+o(1))(\ln n)^{1/3}(\ln\ln n)^{2/3}\bigr),\qquad c=\sqrt[3]{64/9}\approx1.92$$

RSA-240（795 位）于 2019 年用 NFS 完成分解。

示例

• Pollard ρ 分解 $91$：$f(x)=x^2+1$，$x_0=y_0=1$。$x_1=2$，$y_1=5$，$\gcd(3,91)=1$；$x_2=5$，$y_2=40$，$\gcd(35,91)=7$ → $91=7\cdot13$
• Pollard p−1 分解 $1829=31\cdot59$：$31-1=30=2\cdot3\cdot5$ 是 $5$-光滑，取 $B=5$，$M=\operatorname{lcm}(1,\dots,5)=60$；$2^{60}\equiv63\pmod{1829}$，$\gcd(62,1829)=31$ → 得因子 $31$

应用

与离散对数问题并列为经典困难问题；Shor算法在量子计算机上多项式时间分解大整数，直接推动以格基约化算法为代表的后量子密码研究。