质因数分解

1. 什么是质因数分解

质因数分解（Prime Factorization）是将一个大于 1 的正整数表示为若干质数（素数）乘积的过程。例如 360 = 2³ × 3² × 5。这不是一种可选的数学技巧——它是整数的本质结构，就像化学分子式揭示了物质的原子组成一样。

算术基本定理（Fundamental Theorem of Arithmetic）

这个定理有两个关键部分：

• 存在性——每个整数 > 1 都能被分解成质数的乘积（如果本身就是质数，则乘积只有一项）。
• 唯一性——这种分解方式本质上只有一种（忽略因子的排列顺序）。

历史

欧几里得（Euclid，约公元前 300 年）在《几何原本》第九卷中首次阐述了存在性：每个合数都能被某个质数整除。但他没有证明唯一性。

唯一性的严格证明要等到将近两千年后——卡尔·弗里德里希·高斯（Carl Friedrich Gauss）在 1801 年出版的里程碑著作《Disquisitiones Arithmeticae》（算术研究）中给出了完整证明。这部著作奠定了现代数论的基础。

为什么唯一性如此重要？

如果质因数分解不是唯一的，整个数论体系将会崩塌。例如：

• GCD（最大公约数）和 LCM（最小公倍数）的计算将变得不确定。
• RSA 加密算法的安全性假设将不再成立。
• 分数化简可能产生不同的"最简形式"。

事实上，在某些代数结构（如 ℤ[√-5]）中，唯一分解性确实不成立——这正是 Ernst Kummer 和 Richard Dedekind 在 19 世纪发展理想理论（ideal theory）的直接动因。

2. 逐步算法：试除法

试除法（Trial Division）是最古老、最直观的质因数分解算法。它的核心思想极为简单：从最小的质数开始，逐个尝试整除。

算法步骤

1. 从最小的质数 p = 2 开始。
2. 如果 n 能被 p 整除（n mod p = 0），则 p 是 n 的一个质因数。记录 p，并令 n = n / p。
3. 重复步骤 2，直到 n 不再能被 p 整除。
4. 将 p 增加到下一个质数（3, 5, 7, 11, ...），回到步骤 2。
5. 当 p × p > n 时停止。如果此时 n > 1，则 n 本身是一个质因数。

为什么只需检查到 √n？

这是一个关键优化，其数学证明如下：

这意味着如果在 2 到 √n 的范围内都找不到因子，那么 n 一定是质数。这将搜索空间从 n 缩小到了 √n。

时间复杂度

试除法的时间复杂度为 O(√n)。对于 n = 10¹²，最多需要检查约 10⁶ 个除数——现代计算机可以在毫秒内完成。但对于 n = 10¹⁰⁰（如 RSA 密钥），√n = 10⁵⁰，即使是最快的超级计算机也无法在宇宙寿命内完成。

代码实现（JavaScript）

以 360 为例的完整分解过程

结果：360 = 2³ × 3² × 5

3. 大数分解的著名算法

试除法对于小数字已经足够，但当数字增长到几十位甚至上百位时，我们需要更高效的算法。下面按历史顺序和复杂度介绍关键算法。

埃拉托斯特尼筛法（Sieve of Eratosthenes）

发明者：昔兰尼的埃拉托斯特尼（Eratosthenes of Cyrene），约公元前 240 年。他还以精确测量地球周长而闻名。

思想：不是检验单个数字的素性，而是系统地筛除所有合数。从 2 开始，标记 2 的所有倍数为合数；然后找到下一个未标记的数（3），标记它的所有倍数；以此类推。剩下的未标记数全部是质数。

用途：在质因数分解中，我们可以先用筛法生成质数表，然后只用质数做试除，跳过所有合数除数。

费马因式分解（Fermat's Factorization）

发明者：皮埃尔·德·费马（Pierre de Fermat），1643 年。

核心思想：将 n 表示为两个平方数之差：n = a² - b² = (a + b)(a - b)。从 a = ⌈√n⌉ 开始，检查 a² - n 是否为完全平方数。

优势：当 n 的两个因子接近 √n 时（例如 RSA 半素数的两个因子长度接近），费马方法可以极快地找到分解。这也是为什么 RSA 要求两个质因子的大小不能太接近。

Pollard's Rho 算法

发明者：John Pollard，1975 年发表。

核心思想：利用伪随机序列和生日悖论。定义迭代函数 f(x) = (x² + c) mod n，同时维护两个速度不同的迭代器（Floyd 环检测），计算它们差值与 n 的 GCD。当 GCD 不等于 1 也不等于 n 时，就找到了一个非平凡因子。

复杂度：期望 O(n^1/4)——远优于试除法的 O(n^1/2)。对于 20-25 位的数字效果极佳。

代码：Pollard's Rho（JavaScript）

二次筛法（Quadratic Sieve）与一般数域筛法（GNFS）

二次筛法由 Carl Pomerance 于 1981 年提出，是第一个实用的亚指数分解算法。它通过在筛选区间内寻找"光滑数"（只有小质因子的数），构建线性方程组来找到 n 的因子。

一般数域筛法（General Number Field Sieve，GNFS）是目前已知最快的大整数分解算法。它在代数数域中工作，利用格约化（lattice reduction）和复杂的筛选策略。2020 年，GNFS 成功分解了 RSA-250（829 位二进制，250 位十进制），这是目前的世界纪录。

4. 关键公式与性质

一旦得到质因数分解 n = p₁^a₁ × p₂^a₂ × ... × p_k^a_k，我们可以直接计算许多重要的数论函数。

约数个数函数 τ(n)

为什么这个公式成立？（组合论证）

n 的任何约数 d 都具有形式 d = p₁^b₁ × p₂^b₂ × ... × p_k^b_k，其中 0 ≤ b_i ≤ a_i。对于每个质因子 p_i，指数 b_i 有 (a_i + 1) 种选择（从 0 到 a_i）。由乘法原理，约数总数 = 各质因子选择数之积。

例子：360 = 2³ × 3² × 5¹，所以 τ(360) = (3+1)(2+1)(1+1) = 4 × 3 × 2 = 24。

约数和函数 σ(n)

推导：对每个质因子 p_i，其贡献的约数为 p_i⁰ + p_i¹ + ... + p_i^a_i。这是一个等比级数，求和公式为 (p_i^a_i+1 - 1) / (p_i - 1)。由于约数和函数是积性函数，总和等于各质因子贡献之积。

例子：σ(360) = (2⁴-1)/(2-1) × (3³-1)/(3-1) × (5²-1)/(5-1) = 15 × 13 × 6 = 1170。

欧拉函数 φ(n)

谁：莱昂哈德·欧拉（Leonhard Euler），1763 年引入。欧拉函数 φ(n) 计算 1 到 n 中与 n 互质的正整数个数。

为什么重要：

• RSA 加密的核心：密钥生成依赖 φ(n) = (p-1)(q-1)。
• 欧拉定理：若 gcd(a, n) = 1，则 a^φ(n) ≡ 1 (mod n)——这是费马小定理的推广。
• 群论中的阶：φ(n) 等于整数模 n 乘法群 (ℤ/nℤ)* 的阶。

例子：φ(360) = 360 × (1 - 1/2) × (1 - 1/3) × (1 - 1/5) = 360 × 1/2 × 2/3 × 4/5 = 96。

公式汇总表

5. 实际应用

RSA 加密

RSA（Rivest, Shamir, Adleman，1977）是现代互联网安全的基石。其安全性完全依赖于大整数分解的困难性。

原理：选择两个大质数 p 和 q（各约 150-300 位），计算 n = p × q。公钥包含 n，但要从 n 恢复 p 和 q（即分解 n）在计算上极其困难。解密需要 φ(n) = (p-1)(q-1)，而计算 φ(n) 等价于分解 n。

当前纪录：RSA-250（250 位十进制，829 位二进制），于 2020 年被分解，耗费约 2700 CPU 年的计算量。现实中使用的 RSA-2048（617 位十进制）在现有技术下被认为是安全的。

量子威胁：Peter Shor 于 1994 年提出的量子算法可以在多项式时间内分解大整数。如果大规模量子计算机实现，RSA 将不再安全——这推动了后量子密码学（post-quantum cryptography）的研究。

GCD 和 LCM 计算

给定两个数的质因数分解：

• GCD = 各共有质因子取最小指数之积
• LCM = 各出现过的质因子取最大指数之积

例如：360 = 2³ × 3² × 5，150 = 2 × 3 × 5²

• GCD(360, 150) = 2¹ × 3¹ × 5¹ = 30
• LCM(360, 150) = 2³ × 3² × 5² = 1800

分数化简

将分数 a/b 化简为最简形式，本质上就是计算 GCD(a, b) 然后同除。质因数分解让我们可以直观地看到哪些因子可以约去。例如 120/360 = (2³×3×5) / (2³×3²×5) = 1/3。

数论中的应用

• 完美数（Perfect Numbers）：σ(n) = 2n 的数。欧拉证明了所有偶完美数的形式为 2^p-1(2^p - 1)，其中 2^p - 1 是梅森质数。
• 亲和数（Amicable Numbers）：两个数 a, b 满足 σ(a) - a = b 且 σ(b) - b = a。最小的一对是 220 和 284。
• 密码学中的离散对数：质因数分解也与离散对数问题密切相关，影响 Diffie-Hellman 和 ElGamal 加密方案的安全性。

6. 著名数字与故事

梅森质数（Mersenne Primes）

形如 M_p = 2^p - 1 的质数以法国修道士马林·梅森（Marin Mersenne，1588-1648）命名。梅森于 1644 年声称对 p ≤ 257 列出了所有使 M_p 为质数的 p 值——虽然他的列表有几处错误，但这激发了数百年的研究。

为什么特别：梅森质数是已知最大质数的来源。当前纪录保持者是 2^82,589,933 - 1（约 2490 万位），由 GIMPS（互联网梅森质数大搜索）项目于 2018 年发现。GIMPS 是一个分布式计算项目，任何人都可以贡献计算资源。

与完美数的联系：欧几里得-欧拉定理告诉我们，每发现一个梅森质数 M_p，就对应一个偶完美数 2^p-1 × M_p。

费马数（Fermat Numbers）

形如 F_n = 2²ⁿ + 1 的数。费马观察到 F₀=3, F₁=5, F₂=17, F₃=257, F₄=65537 都是质数，于是猜想所有费马数都是质数。

反例：莱昂哈德·欧拉于 1732 年证明 F₅ = 4,294,967,297 = 641 × 6,700,417，彻底否定了费马的猜想。此后发现的所有费马数（F₅ 到 F₃₂）要么被证明是合数，要么素性未知。至今没有发现 F₄ 之后的费马质数。

有趣的联系：高斯证明正 n 边形可以用尺规作图，当且仅当 n 是 2 的幂与若干不同费马质数的乘积。这就是为什么正 17 边形（F₂=17）可以尺规作图，而正 7 边形不行。

孪生质数猜想（Twin Prime Conjecture）

猜想存在无穷多组"孪生质数"——相差 2 的质数对，如 (3,5), (11,13), (29,31), (41,43)。

这个猜想至今未被证明。2013 年，张益唐证明存在无穷多对相差不超过 7000 万的质数，这是重大突破。随后 James Maynard 和 Terence Tao 的 Polymath 项目将这个界缩小到 246。但从 246 到 2 的最后一步仍然遥不可及。

哥德巴赫猜想（Goldbach's Conjecture）

1742 年，普鲁士数学家克里斯蒂安·哥德巴赫在写给欧拉的信中提出：每个大于 2 的偶数都可以表示为两个质数之和。例如：4=2+2, 6=3+3, 8=3+5, 10=3+7=5+5, 100=3+97=11+89=17+83=29+71=41+59=47+53。

这可能是数学中最古老的未解决猜想之一。经计算机验证，所有不超过 4 × 10¹⁸ 的偶数都满足猜想，但严格证明仍然缺失。

7. 素性测试

素性测试（判断一个数是否为质数）与质因数分解密切相关但有本质区别：判断一个数是否为质数比找到它的因子要容易得多。

Miller-Rabin 测试

发明者：Gary L. Miller（1976，确定性版本基于广义黎曼假设）和 Michael O. Rabin（1980，概率版本）。

原理：基于费马小定理的逆否命题。将 n-1 写成 2^s × d 的形式，对随机选取的基 a，检查 a^d mod n 是否等于 1 或 -1，以及序列 a^2d, a^4d, ... 中是否出现 -1。

优势：每轮测试的错误概率不超过 1/4。执行 k 轮后，错误概率 ≤ 4^-k。20 轮测试的错误概率约 10^-12，在实际应用中已足够可靠。时间复杂度 O(k × log² n × log log n)。

应用：RSA 密钥生成中寻找大质数的标准方法。OpenSSL、GnuPG 等密码库都使用 Miller-Rabin。

AKS 素性测试

发明者：Manindra Agrawal、Neeraj Kayal、Nitin Saxena，2002 年（印度理工学院坎普尔分校）。

原理：基于一个推广的费马小定理：n 是质数当且仅当多项式恒等式 (x + a)ⁿ ≡ xⁿ + a (mod n) 成立。AKS 算法巧妙地将这个需要检查指数级多项系数的条件简化为可在多项式时间内验证的形式。

复杂度：O(log⁶ n)（原始版本），后续改进至 O(log³ n)（在某些猜想下）。

实际应用：虽然理论上是突破性的，但在实际中 AKS 比 Miller-Rabin 慢得多，因此密码学实现仍然首选 Miller-Rabin。AKS 的价值在于其理论意义——它证明了素性测试在计算复杂性理论中的确切地位。

素性测试对比

*Miller-Rabin 在确定性变体中需要广义黎曼假设。

8. 相关工具

• GCD/LCM 计算器 — 使用欧几里得算法计算最大公约数和最小公倍数，展示详细步骤。
• 模运算计算器 — 模加、模乘、模幂运算，RSA 加密的核心操作。
• 排列组合计算器 — 计算排列数和组合数，约数个数公式的组合论基础。

9. 常见问题