第 31 章数论算法 (Number-Theoretic Algorithms)

核心结论

基本对象：整除（\(d \mid a\)）、素数（> 1 且仅被 1 与自身整除）、互素（gcd = 1）、唯一分解定理（任何合数可唯一分解为素数之积）。
Euclid 算法与扩展 Euclid：用 gcd 递推 \(\gcd(a, b) = \gcd(b, a \bmod b)\) 求最大公因数；扩展版同时返回系数 \(x, y\) 使 \(d = ax + by\)；时间 O(lg b) 次递归。
模运算与群：\((\mathbb{Z}_n, +)\) 是阿贝尔群；\((\mathbb{Z}_n^*, \cdot)\) 是乘法群（当 n 为素数时是循环群）；模逆元用扩展 Euclid 求。
中国剩余定理 (CRT)：若 \(n_i\) 两两互素，则「同时满足 \(x \equiv a_i \pmod{n_i}\)」的系统有唯一解 modulo \(\prod n_i\)；时间 O(n)。
RSA 公钥密码：基于「大整数难分解」假设；密钥生成用大素数 p, q；加密 / 解密用模幂运算；安全依赖因数分解难度。
素性测试 (Miller-Rabin)：随机化多项式时间算法；用 Fermat 小定理 + 二次探测检测合数；误判概率 ≤ 2⁻ᵏ（k 次独立测试）。

本章主旨

数论曾被视为纯数学；今天因 RSA 等密码系统的需求而成为算法核心。本章以「整除 / gcd / 模运算」为基础，逐步构建「模线性方程、CRT、模幂、RSA、素性测试」五个应用层。各层都依赖前一层的工具：Euclid → 模逆 → 模线性方程 → CRT → 模幂 → RSA / Miller-Rabin。理解这一依赖链是掌握本章的关键。

一、核心概念

本章围绕 6 个核心概念展开：从基本整除性出发，先介绍 Euclid 算法与扩展版，然后讨论模运算与中国剩余定理，最后给出模幂与 RSA / Miller-Rabin。

概念	定义 + 重要性	实现提示
整除与 gcd	\(d \mid a\)（a 是 d 的倍数）；gcd(a, b) 是 a, b 的最大公因数；互素 = gcd = 1；唯一分解定理。	§31.1；CLRS 引理 31.2：gcd 是 a, b 的最小正线性组合。
Euclid 算法	递归 \(\gcd(a, b) = \gcd(b, a \bmod b)\)；时间 O(lg b) 次递归；最坏输入是相邻 Fibonacci 数（Lamé 定理）。	§31.2；扩展版同时返回 x, y 使 d = ax + by；用于求模逆元。
模运算与群	\(a \equiv b \pmod{n}\)；\((\mathbb{Z}_n, +)\) 群；\((\mathbb{Z}_n^*, \cdot)\) 群（n 素时是循环群）；欧拉函数 \(\phi(n)\) 与 Fermat 小定理。	§31.3；扩展 Euclid 用于求模逆。
中国剩余定理 (CRT)	若 \(n_i\) 两两互素，则「同余方程组 \(x \equiv a_i \pmod{n_i}\)」有唯一解 modulo \(N = \prod n_i\)；时间 O(n)。	§31.5；用模逆构造解。
模幂 (Modular exponentiation)	重复平方算法求 \(a^b \bmod n\)，时间 O(lg b) 次乘法；是 RSA 加解密、素性测试的核心。	§31.6；递归式：若 b 偶则 (a^{b/2})²；若 b 奇则 a · (a^{(b-1)/2})²。
RSA 公钥密码	公钥 (n, e)，私钥 d；加密 c = m^e mod n，解密 m = c^d mod n；安全依赖「n = pq 难分解」。	§31.7；密钥生成 + 加密 + 解密；正确性由 Fermat 小定理保证。

概念

定义 + 重要性

实现提示

整除与 gcd

\(d \mid a\)（a 是 d 的倍数）；gcd(a, b) 是 a, b 的最大公因数；互素 = gcd = 1；唯一分解定理。

§31.1；CLRS 引理 31.2：gcd 是 a, b 的最小正线性组合。

Euclid 算法

递归 \(\gcd(a, b) = \gcd(b, a \bmod b)\)；时间 O(lg b) 次递归；最坏输入是相邻 Fibonacci 数（Lamé 定理）。

§31.2；扩展版同时返回 x, y 使 d = ax + by；用于求模逆元。

模运算与群

\(a \equiv b \pmod{n}\)；\((\mathbb{Z}_n, +)\) 群；\((\mathbb{Z}_n^*, \cdot)\) 群（n 素时是循环群）；欧拉函数 \(\phi(n)\) 与 Fermat 小定理。

§31.3；扩展 Euclid 用于求模逆。

中国剩余定理 (CRT)

若 \(n_i\) 两两互素，则「同余方程组 \(x \equiv a_i \pmod{n_i}\)」有唯一解 modulo \(N = \prod n_i\)；时间 O(n)。

§31.5；用模逆构造解。

模幂 (Modular exponentiation)

重复平方算法求 \(a^b \bmod n\)，时间 O(lg b) 次乘法；是 RSA 加解密、素性测试的核心。

§31.6；递归式：若 b 偶则 (a^{b/2})²；若 b 奇则 a · (a^{(b-1)/2})²。

RSA 公钥密码

公钥 (n, e)，私钥 d；加密 c = m^e mod n，解密 m = c^d mod n；安全依赖「n = pq 难分解」。

§31.7；密钥生成 + 加密 + 解密；正确性由 Fermat 小定理保证。

二、详细笔记

31.1 整除、gcd 与唯一分解

What：整除性是数论的基础；\(\gcd(a,b)\) 是 a, b 的最大公因数；任意正整数可唯一分解为素数之积。

Why：整除性是后续所有数论算法的基石——Euclid、模运算、CRT、RSA 都建立其上；唯一分解定理保证「素数是整数的原子」。

How：

核心定义：

\(d \mid a\)：d 整除 a；a = kd（某整数 k）。
素数：仅被 1 与自身整除的 > 1 整数；合数 = 非素非 1。
\(\gcd(a, b)\)：a, b 的最大公因数；定义 \(\gcd(0,0) = 0\)。
互素：\(\gcd(a,b) = 1\)。
算术基本定理（定理 31.8）：任何 > 1 的整数可唯一写成素数之积。

gcd 的关键性质（式 31.6-31.10）：

交换律：\(\gcd(a,b) = \gcd(b,a)\)。
缩放：\(\gcd(an, bn) = n \gcd(a,b)\)（推论 31.4）。
互素传播：若 \(\gcd(a,p) = \gcd(b,p) = 1\)，则 \(\gcd(ab, p) = 1\)（定理 31.6）。

定理 31.2：gcd(a, b) 是 a, b 的最小正整数线性组合 \(ax + by\)。

When：任何「求最大公因数」「判定互素」「质因数分解」相关问题。

Example：gcd(24, 30) = 6；6000 = 2⁴ · 3 · 5³；gcd(8, 15) = 1（互素）。

31.2 Euclid 算法与扩展版本

What：Euclid 用递推 \(\gcd(a, b) = \gcd(b, a \bmod b)\) 求 gcd；扩展版同时返回系数 x, y 使 \(d = ax + by\)，时间 O(lg b) 次递归。

Why：朴素「分解素因子再求 min 指数」需要分解（难）；Euclid 是多项式时间算法；扩展版是求模逆元的核心工具。

How：

EUCLID(a, b)：

if b = 0: return a
else return EUCLID(b, a mod b)

复杂度分析（Lamé 定理 31.11）：递归次数 ≤ \(1 + \log_\phi b\)；最坏输入是相邻 Fibonacci 数。

扩展版 EXTENDED-EUCLID(a, b)：

if b = 0: return (a, 1, 0)
else (d', x', y') = EXTENDED-EUCLID(b, a mod b)
return (d', y', x' - ⌊a/b⌋ · y')

正确性：归纳可得 \(d = ax + by\)；x, y 可负。

应用：

求模逆元：若 \(\gcd(a, n) = 1\)，则 EXTENDED-EUCLID(a, n) 返回 (1, x, y)，使 \(ax \equiv 1 \pmod{n}\)，x 即逆元。
模线性方程求解（§31.4）。

When：求 gcd；求模逆元；模线性方程求解；密码学实现。

Example：EUCLID(30, 21) = EUCLID(21, 9) = EUCLID(9, 3) = EUCLID(3, 0) = 3。EXTENDED-EUCLID(99, 78) = (3, -11, 14)，验证 3 = 99·(-11) + 78·14。

31.3 模运算与群

What：模运算 \(a \equiv b \pmod{n}\) 把整数按余数分类；\((\mathbb{Z}_n, +)\) 与 \((\mathbb{Z}_n^*, \cdot)\) 是群；模逆元由扩展 Euclid 求。

Why：模运算是「整数上的循环运算」——密码学、散列、伪随机生成的基础；群论为模运算提供抽象框架。

How：

核心定义：

\(a \equiv b \pmod{n}\)：\(n \mid (a-b)\)；等价类 \([a\)_n] = \(\{a + kn : k \in \mathbb{Z}\}\)。
\(\mathbb{Z}_n = \{[0\)_n, [1]_n, \ldots, [n-1]_n\}]（式 31.1）。

群 (S, ⊕)：

封闭、结合、单位元、逆元四公理。
阿贝尔群：满足交换律。
有限群：|S| < ∞。

模加群 (ℤₙ, +)：阿贝尔群；逆元 = -a mod n；单位元 = 0。

模乘群 (ℤₙ*, ·)：单位元 = 1；逆元存在 iff \(\gcd(a, n) = 1\)。

欧拉函数：\(\phi(n) = |\{a : 1 \leq a \leq n, \gcd(a,n)=1\}|\)；性质：

n 素：\(\phi(n) = n-1\)。
n = pq（p, q 素）：\(\phi(n) = (p-1)(q-1)\)。
积性：\(\phi(mn) = \phi(m) \phi(n)\)（m, n 互素）。

Fermat 小定理：若 p 素且 p ∤ a，则 \(a^{p-1} \equiv 1 \pmod{p}\)。

Euler 定理：若 \(\gcd(a,n) = 1\)，则 \(a^{\phi(n)} \equiv 1 \pmod{n}\)。

When：模运算（密码学、散列、循环队列）；群论应用于对称性 / 不变量分析。

Example：\(\mathbb{Z}_7^* = \{1, 2, 3, 4, 5, 6\}\)，\(\phi(7) = 6\)；\(3^6 = 729 \equiv 1 \pmod{7}\)。

31.4 模线性方程与 CRT

What：解模线性方程 \(ax \equiv b \pmod{n}\) 用扩展 Euclid 求模逆；CRT 把多个同余方程合成单个。

Why：很多问题可化为模线性方程；CRT 用于大整数表示（分解为多个小模数）、并行计算、密码学。

How：

模线性方程求解：

方程 \(ax \equiv b \pmod{n}\) 有解 ⟺ \(\gcd(a, n) \mid b\)。
有解时通解 \(x = x_0 + (n/d) k\) for k = 0, 1, …, d-1（d = gcd(a, n)）。
算法：EXTENDED-EUCLID(a, n) 返回 (d, x', y')；若 d ∤ b 则无解；否则 x = x' · (b/d) mod (n/d)。

中国剩余定理（CRT）：

系统：\(x \equiv a_i \pmod{n_i}\) for i = 1, …, k；其中 \(n_i\) 两两互素。
解：\(x = \sum_{i=1}^k a_i N_i y_i \bmod N\)，其中 \(N = \prod n_i\)，\(N_i = N/n_i\)，\(y_i = N_i^{-1} \bmod n_i\)。
唯一性：解唯一 modulo N。
时间：O(n)（含模逆计算）。

实际应用：

大整数表示：拆成多个 32 位数（n_i = 2^32）；并行加减乘。
RSA 加速：CRT-RSA 把模幂拆为 p, q 上的两个模幂，时间 4 倍加速。

When：模线性方程；大整数运算；并行化模幂；密码学实现。

Example：解 x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7)：N = 105，N₁ = 35, y₁ = 35⁻¹ mod 3 = 2；x = 2·35·2 + 3·21·1 + 2·15·1 = 140 + 63 + 30 = 233 ≡ 23 (mod 105)。

31.5 模幂与重复平方

What：用重复平方算法在 O(lg b) 次模乘内计算 \(a^b \bmod n\)；是 RSA / Miller-Rabin 的核心操作。

Why：直接 b 次模乘对大 b 不可行（如 b = 2²⁰⁴⁸）；重复平方用二进制分解把 O(b) 降到 O(lg b)。

How：

MODULAR-EXPONENTIATION(a, b, n)：

if b = 0: return 1
(c, d) = MODULAR-EXPONENTIATION(a, ⌊b/2⌋, n)
if b 偶: return (c · c) mod n
else: return (c · c · a) mod n

复杂度：O(lg b) 次递归 + 每次 O(1) 模乘（若 a, b, n 视为「机器字长」则单次模乘 O(1)；若视为 β 位则 O(β²) 位运算）。

应用：

RSA 加解密：c = m^e mod n，m = c^d mod n（e, d 是公私钥）。
素性测试（Miller-Rabin）：a^d mod n。
Diffie-Hellman 密钥交换：g^{ab} mod p。

When：任何模幂运算；密码学；数论算法（素性测试、分解）。

Example：计算 2¹³ mod 100：13 = 1101₂ → 2¹ · (2²)² · ((2²)²)² = 2 · 4² · 16² = 2 · 16 · 256 = 8192 ≡ 92 (mod 100)。

31.6 RSA 公钥密码

What：RSA 是公钥密码系统；公钥 (n, e)，私钥 d；加密 c = m^e mod n，解密 m = c^d mod n；安全基于「大整数难分解」。

Why：RSA 是 Internet 安全的基石（SSL/TLS、数字签名）；理解其结构是计算机科学家的必备知识。

How：

密钥生成：

选两个大素数 p, q（n/2 位，各 1024 位）；n = pq。
选 e 与 \(\phi(n) = (p-1)(q-1)\) 互素。
求 d = e⁻¹ mod \(\phi(n)\)（扩展 Euclid）。
公钥 = (n, e)；私钥 = d（p, q 销毁）。

加密 / 解密：

加密：\(c = m^e \bmod n\)。
解密：\(m = c^d \bmod n\)。

正确性：m^{ed} ≡ m^{1 + kφ(n)} ≡ m (mod n)（Fermat-Euler 定理）。

安全性：若能从 n 分解出 p, q 则可求 d；目前大整数分解亚指数但非多项式。

实际应用：

SSL/TLS 握手。
数字签名（私钥加密、公钥验证）。
PGP / GPG 邮件加密。

When：公钥加密；数字签名；密钥交换；任何需要非对称密码的场景。

Example：p=5, q=11, n=55, φ=40, e=3, d=27（3·27=81≡1 mod 40）。加密 m=4：c = 4³ = 64 ≡ 9 (mod 55)；解密：9²⁷ mod 55 = 4。

31.7 素性测试 (Miller-Rabin)

What：Miller-Rabin 是随机化多项式时间素性测试；用 Fermat 小定理 + 二次探测检测合数；单次测试误判概率 ≤ 1/4，k 次独立测试 ≤ 4⁻ᵏ。

Why：RSA 需要大素数生成；确定性多项式素性测试（AKS 2002）常数极大；Miller-Rabin 是实践中标准。

How：

算法：

写 n-1 = 2^s · d（d 奇）。
随机选 a ∈ [2, n-2]。
计算 x₀ = a^d mod n。
若 x₀ = 1 或 x₀ = n-1：返回「可能素数」。
for i = 1 to s-1:
1. 计算 xᵢ = xᵢ₋₁² mod n。
2. 若 xᵢ = n-1：返回「可能素数」。
否则返回「合数」。

复杂度：O(s · M(β)) 位运算，s ≤ lg(n)；约 O(β³)。

单次测试正确率：合数通过测试的概率 ≤ 1/4（用二次探测的非平凡平方根的性质）。

k 次独立测试：通过概率 ≤ 4⁻ᵏ（k=20 时 ≈ 10⁻¹²）。

When：RSA 密钥生成；密码学实现；数论算法；任何需要「判定大整数素性」的场景。

Example：测试 n = 221 = 13·17：221-1 = 220 = 2² · 55，s=2, d=55。a = 174：x₀ = 174^55 mod 221 = 47；x₁ = 47² mod 221 = 220 = n-1 → 返回「可能素数」。a = 137：x₀ = 137^55 mod 221 = 188；x₁ = 188² mod 221 = 205 ≠ 220 → 返回「合数」。

三、关键图表

核心公式对照表

公式编号

内容

式 31.1

同余类 \(\mathbb{Z}_n = \{[0\)_n, [1]_n, \ldots, [n-1]_n\}]

式 31.6-31.10

gcd 基本性质（交换律、缩放等）

式 31.13

\(\gcd(a,b) = \prod p_i^{\min(e_i, f_i)}\)

定理 31.2

gcd(a, b) = a, b 的最小正线性组合

推论 31.4

\(\gcd(an, bn) = n \gcd(a,b)\)

推论 31.5

整除传递性：\(n \mid ab\) 且 \(\gcd(a,n)=1\) ⟹ \(n \mid b\)

定理 31.6

互素传播：\(\gcd(a,p) = \gcd(b,p) = 1\) ⟹ \(\gcd(ab,p) = 1\)

定理 31.8

唯一分解定理

定理 31.9

gcd 递推：\(\gcd(a,b) = \gcd(b, a \bmod b)\)

引理 31.10

Euclid 调用次数 k ⟹ \(a \geq F_{k+2}\)

定理 31.11

Lamé 定理：递归次数 ≤ 1 + log_φ b

Fermat 小定理

p 素且 p ∤ a ⟹ \(a^{p-1} \equiv 1 \pmod{p}\)

Euler 定理

\(\gcd(a,n)=1\) ⟹ \(a^{\phi(n)} \equiv 1 \pmod{n}\)

RSA

n = pq, ed ≡ 1 (mod φ(n)) ⟹ \(m^{ed} \equiv m \pmod{n}\)

四、思维导图

mindmap
  root((第 31 章 数论算法))
    基础
      整除
      素数
      gcd
      唯一分解
    Euclid算法
      gcd递归
      扩展版
      模逆元
      Lamé定理
    模运算
      同余类
      群结构
      Fermat小定理
      Euler定理
    CRT
      同余方程组
      唯一解
      大整数表示
    模幂
      重复平方
      O(lgb)
      RSA核心
    RSA
      公钥私钥
      加密解密
      安全性
      大素数
    素性测试
      Miller-Rabin
      二次探测
      随机化
      误判率4⁻ᵏ

五、重点与易错点

整除性 d∣a：d = 0 时 0∣a 仅在 a = 0 时成立——避免「除以 0」的混淆。
gcd(0, 0) = 0 是约定：让 gcd 的性质（如 gcd(a, 0) = |a|）普遍成立。
Euclid 算法的「最坏输入」：相邻 Fibonacci 数 — Lamé 定理的精确上界。
扩展 Euclid 的返回值：(d, x, y) 使 d = ax + by；x, y 可负或 0。
模逆元的存在性条件：\(a^{-1} \bmod n\) 存在 ⟺ \(\gcd(a,n) = 1\)；否则无解。
CRT 要求 \(n_i\) 两两互素：若不互素则解可能不存在或多个；用推广 CRT 处理。
Euler 函数 \(\phi(n)\) 的积性：当 m, n 互素时 \(\phi(mn) = \phi(m)\phi(n)\)；推论：\(\phi(p^k) = p^{k-1}(p-1)\)。
Fermat 小定理与素性判定：满足 \(a^{n-1} \equiv 1 \pmod{n}\) 的合数是「Fermat 伪素数」；可用作必要条件但不充分。
模幂的「位运算」成本：朴素模乘 O(β²) 位运算；FFT / NTT 加速可达 O(β lg β lg lg β)；实践中朴素版对 1024-2048 位足够。
RSA 密钥长度的选择：当前 2048 位是工业标准；4096 位更安全但慢；小于 1024 位已被破解。
p, q 的选择：要随机选且接近（防 Pollard p-1 攻击）；同时 \(\phi(n) = (p-1)(q-1)\) 不能太平滑。
Miller-Rabin 的「确定性」版本：若 a 取遍所有 a ∈ [2, 2(\ln n)²]，则结果确定（Monier-Rabin 定理）；实践中 k=20 随机测试足够。
与第 1 章问题的衔接：数论算法曾被视为无用；今天因 RSA 等成为必备；NP-hard 问题（如分解）的「难」是密码学的基础。
与第 26 章最大流的衔接：最大流的整数值性源于「边权为整数 + 流量守恒」；数论的整数结构在组合算法中处处体现。
实际工具：OpenSSL（RSA 实现）、GMP（多精度整数库）、Python crypto 库、GnuPG（PGP 实现）。

第 31 章 数论算法 (Number-Theoretic Algorithms)

核心结论

一、核心概念

二、详细笔记

31.1 整除、gcd 与唯一分解

31.2 Euclid 算法与扩展版本

31.3 模运算与群

31.4 模线性方程与 CRT

31.5 模幂与重复平方

31.6 RSA 公钥密码

31.7 素性测试 (Miller-Rabin)

三、关键图表

四、思维导图

五、重点与易错点

第 31 章数论算法 (Number-Theoretic Algorithms)