第4章 数论进阶 (Advanced Number Theory)
一、导读
4.1 本章学习目标
在本章结束时，你将能够：
- 理解同余方程的求解方法
- 掌握中国剩余定理及其实际应用
- 运用费马小定理和欧拉定理解决模幂问题
- 理解二次剩余和勒让德符号
- 应用数论函数如莫比乌斯函数、除数函数
- 理解连分数的基本概念
- 掌握素性测试的基本算法
- 了解椭圆曲线在密码学中的应用基础
4.2 为什么本章如此重要
第3章介绍了数论的基础概念，本章将深入探讨更高级的数论主题。这些内容在现代密码学、编码理论、算法设计中有着直接应用。
中国剩余定理是分布式计算和大数运算的核心工具。二次剩余理论在密码协议（如Rabin加密）中扮演关键角色。素性测试是生成RSA密钥的基础。
对于程序员而言，掌握这些高级数论技巧意味着能够：
设计和分析基于数论的加密算法
处理大整数运算中的效率问题
理解现代密码系统的安全基础
解决竞赛编程中的数论难题
优化涉及模运算的算法性能
数论虽然古老，但在计算机科学中焕发新生。从哈希函数的设计到随机数生成，从错误检测码到区块链共识机制，数论无处不在。本章将帮助你建立坚实的数论基础，为后续学习密码学和高级算法打下根基。
4.3 核心问题引导
如何求解多个同余方程组成的方程组？
中国剩余定理的条件是什么？解是否唯一？
什么是二次剩余？如何判断一个数是否是模p的二次剩余？
莫比乌斯反演公式是什么？它在组合数学中有何应用？
如何高效测试一个大数是否为素数？
连分数如何用于逼近无理数？
欧拉定理与费马小定理有什么关系？
离散对数问题为何在密码学中如此重要？
二、核心概念详解
4.1 中国剩余定理
问题引入
考虑以下问题：
- 一个数除以3余2
- 除以5余3
- 除以7余2
- 求这个数
这是《孙子算经》中的经典问题。用同余语言表述：
$$x \equiv 2 \pmod{3}$$
$$x \equiv 3 \pmod{5}$$
$$x \equiv 2 \pmod{7}$$
中国剩余定理（Chinese Remainder Theorem, CRT）给出了这类方程组的解法。
定理陈述
定理（中国剩余定理）：设 m₁, m₂, ..., mₖ 是两两互质的正整数，M = m₁m₂...mₖ。则对任意整数 a₁, a₂, ..., aₖ，同余方程组：
$$x \equiv a_1 \pmod{m_1}$$
$$x \equiv a_2 \pmod{m_2}$$
$$\vdots$$
$$x \equiv a_k \pmod{m_k}$$
有唯一解 x ≡ a (mod M)，其中 0 ≤ a < M。
唯一性证明：假设 x 和 y 都是解，则 x ≡ y (mod mᵢ) 对所有 i 成立。由于 mᵢ 两两互质，这意味着 x - y 能被所有 mᵢ 整除，即 x - y 能被 M 整除。因此 x ≡ y (mod M)。在 [0, M) 范围内，解是唯一的。
构造性证明与算法
步骤1：计算 M = m₁m₂...mₖ。
步骤2：对每个 i，计算 Mᵢ = M/mᵢ。
步骤3：对每个 i，计算 yᵢ = Mᵢ⁻¹ mod mᵢ（即 Mᵢ 模 mᵢ 的逆元）。
步骤4：解为 $x = \sum_{i=1}^{k} a_i M_i y_i \pmod{M}$。
验证：对任意 j，x mod mⱼ = aⱼMⱼyⱼ mod mⱼ + Σ_{i≠j} aᵢMᵢyᵢ mod mⱼ。
由于 Mᵢ 包含 mⱼ 作为因子（当 i ≠ j），所以 Mᵢ ≡ 0 (mod mⱼ)。
而 Mⱼyⱼ ≡ 1 (mod mⱼ)，所以 x ≡ aⱼ × 1 ≡ aⱼ (mod mⱼ)。✓
逆元的存在性：由于 mᵢ 与 Mᵢ 互质（因为 mᵢ 与其他所有 mⱼ 互质），根据贝祖定理，存在整数 yᵢ 使得 Mᵢyᵢ ≡ 1 (mod mᵢ)。这个 yᵢ 可以通过扩展欧几里得算法求得。
示例求解
回到孙子问题：
- m₁=3, m₂=5, m₃=7，M = 105
- M₁ = 35, M₂ = 21, M₃ = 15
- y₁ = 35⁻¹ mod 3 = 2⁻¹ mod 3 = 2（因为 2×2=4≡1 mod 3）
- y₂ = 21⁻¹ mod 5 = 1⁻¹ mod 5 = 1
- y₃ = 15⁻¹ mod 7 = 1⁻¹ mod 7 = 1
$x = 2 \times 35 \times 2 + 3 \times 21 \times 1 + 2 \times 15 \times 1 = 140 + 63 + 30 = 233$
233 mod 105 = 23。验证：23 mod 3 = 2 ✓，23 mod 5 = 3 ✓，23 mod 7 = 2 ✓。
代码实现
def chinese_remainder_theorem(remainders, moduli):
"""
中国剩余定理
参数:
remainders: [a1, a2, ..., ak]
moduli: [m1, m2, ..., mk]，必须两两互质
返回: x mod M，其中 M = m1*m2*...*mk
"""
def extended_gcd(a, b):
if b == 0:
return a, 1, 0
g, x1, y1 = extended_gcd(b, a % b)
return g, y1, x1 - (a // b) * y1
def mod_inverse(a, m):
g, x, _ = extended_gcd(a, m)
if g != 1:
raise ValueError("逆元不存在")
return x % m
M = 1
for m in moduli:
M *= m
x = 0
for ai, mi in zip(remainders, moduli):
Mi = M // mi
yi = mod_inverse(Mi, mi)
x += ai * Mi * yi
return x % M
# 测试孙子问题
remainders = [2, 3, 2]
moduli = [3, 5, 7]
result = chinese_remainder_theorem(remainders, moduli)
print(f"孙子问题的解: x = {result}") # 应该是 23
# 测试另一个例子：x ≡ 1 (mod 2), x ≡ 2 (mod 3), x ≡ 3 (mod 5)
remainders2 = [1, 2, 3]
moduli2 = [2, 3, 5]
result2 = chinese_remainder_theorem(remainders2, moduli2)
print(f"第二个例子的解: x = {result2}") # 应该是 23应用场景
大数运算：将大数分解为多个小数进行并行计算。例如，要计算两个大数 A 和 B 的乘积，可以先将它们分别对一组小模数取余，在小模数域中进行乘法，最后用CRT还原结果。这种方法可以避免大数运算的开销。
密码学：RSA解密时使用CRT加速。RSA私钥解密操作 m = c^d mod n 可以分解为两个较小的模幂运算：m₁ = c^d mod p 和 m₂ = c^d mod q，然后用CRT合并。这使得解密速度提高约4倍。
秘密共享：Shamir秘密共享方案的变体。将秘密 s 编码为一个多项式的常数项，每个参与者获得多项式在某点的值。恢复秘密需要足够多的点，这等价于求解一个同余方程组。
编码理论：纠错码的设计。某些循环码的编解码算法利用CRT在多项式环中的性质。
分布式系统：在分布式数据库中，使用CRT可以将数据分片存储在不同的节点上，查询时通过CRT合并结果。
广义中国剩余定理
当模数不两两互质时，方程组可能有解也可能无解。广义CRT给出了解存在的条件：
方程组 x ≡ aᵢ (mod mᵢ) 有解当且仅当对所有 i, j，有 aᵢ ≡ aⱼ (mod gcd(mᵢ, mⱼ))。
如果有解，解在模 lcm(m₁, m₂, ..., mₖ) 下唯一。
4.2 费马小定理与欧拉定理
费马小定理
定理（费马小定理）：如果 p 是素数，a 是任意整数且 p ∤ a，则：
$$a^{p-1} \equiv 1 \pmod{p}$$
等价形式：对任意整数 a，有 $a^p \equiv a \pmod{p}$。
证明：考虑集合 {a, 2a, 3a, ..., (p-1)a} mod p。由于 p ∤ a，这些元素两两不同 mod p（如果 ia ≡ ja (mod p)，则 (i-j)a ≡ 0 (mod p)，由于 p ∤ a，必有 p | (i-j)，但 |i-j| < p，矛盾）。因此这个集合是 {1, 2, ..., p-1} 的一个排列。
将所有元素相乘：a × 2a × ... × (p-1)a ≡ 1 × 2 × ... × (p-1) (mod p)
即 $a^{p-1}(p-1)! \equiv (p-1)! \pmod{p}$
由于 (p-1)! 与 p 互质，可以消去，得到 $a^{p-1} \equiv 1 \pmod{p}$。✓
应用：
- 模幂简化：计算 a^n mod p 时，可以先将 n 对 p-1 取余
- 素性测试：如果 a^{n-1} ≢ 1 (mod n)，则 n 一定是合数
- 逆元计算：a^{-1} ≡ a^{p-2} (mod p)
欧拉定理
欧拉函数 φ(n) 定义为小于等于 n 且与 n 互质的正整数个数。
定理（欧拉定理）：如果 gcd(a, n) = 1，则：
$$a^{\phi(n)} \equiv 1 \pmod{n}$$
证明思路：类似费马小定理的证明。考虑与 n 互质的剩余类 {r₁, r₂, ..., r_φ(n)}。集合 {ar₁, ar₂, ..., ar_φ(n)} mod n 也是与 n 互质的剩余类的一个排列。将所有元素相乘并消去公共因子即可。
费马小定理是欧拉定理的特例：当 n = p 是素数时，φ(p) = p-1。
欧拉函数的性质：
- 如果 p 是素数，φ(p) = p-1
- 如果 p 是素数，φ(p^k) = p^k - p^{k-1} = p^{k-1}(p-1)
- 如果 gcd(m, n) = 1，则 φ(mn) = φ(m)φ(n)（积性函数）
- 一般公式：如果 $n = p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$，则 $\phi(n) = n\prod_{i=1}^{k}(1-\frac{1}{p_i})$
模幂运算的快速算法
计算 a^n mod m 的朴素算法需要 O(n) 次乘法。使用快速幂算法（平方-乘方法），可以在 O(log n) 次乘法内完成。
def fast_pow_mod(base, exp, mod):
"""快速幂算法：计算 base^exp mod mod"""
result = 1
base = base % mod
while exp > 0:
if exp % 2 == 1:
result = (result * base) % mod
exp = exp >> 1
base = (base * base) % mod
return result
# 示例：计算 3^100 mod 101
print(fast_pow_mod(3, 100, 101)) # 根据费马小定理，应该是 14.3 二次剩余
定义
设 p 是奇素数，a 是整数。如果存在整数 x 使得 x² ≡ a (mod p)，则称 a 是模 p 的二次剩余（Quadratic Residue）；否则称为二次非剩余。
示例：模 7 的二次剩余：
- 1² ≡ 1, 2² ≡ 4, 3² ≡ 2, 4² ≡ 2, 5² ≡ 4, 6² ≡ 1 (mod 7)
- 所以 1, 2, 4 是二次剩余，3, 5, 6 是二次非剩余
性质：模 p 恰好有 (p-1)/2 个二次剩余和 (p-1)/2 个二次非剩余（不包括0）。这是因为 x² ≡ (p-x)² (mod p)，所以每个二次剩余恰好有两个平方根。
勒让德符号
勒让德符号（Legendre Symbol）定义为：
$$\left(\frac{a}{p}\right) = \begin{cases}
0 & \text{if } p | a \\
1 & \text{if } a \text{ 是模 } p \text{ 的二次剩余} \\
-1 & \text{if } a \text{ 是模 } p \text{ 的二次非剩余}
\end{cases}$$
性质：
- $(\frac{ab}{p}) = (\frac{a}{p})(\frac{b}{p})$（完全积性）
- $(\frac{a^2}{p}) = 1$ 如果 p ∤ a
欧拉判别准则
定理：设 p 是奇素数，p ∤ a，则：
$$\left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \pmod{p}$$
证明：由费马小定理，a^{p-1} ≡ 1 (mod p)，即 (a^{(p-1)/2})² ≡ 1 (mod p)。
所以 a^{(p-1)/2} ≡ ±1 (mod p)。
- 如果 a 是二次剩余，即 a ≡ x² (mod p)，则 a^{(p-1)/2} ≡ x^{p-1} ≡ 1 (mod p)
- 如果 a 是二次非剩余，可以证明 a^{(p-1)/2} ≡ -1 (mod p)
应用：提供了一个判定二次剩余的算法，时间复杂度为 O(log p)（使用快速幂）。
二次互反律
二次互反律（Quadratic Reciprocity Law）是数论中最优美的定理之一：
定理（高斯）：设 p, q 是不同的奇素数，则：
$$\left(\frac{p}{q}\right)\left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}$$
等价表述：
- 如果 p ≡ 1 (mod 4) 或 q ≡ 1 (mod 4)，则 $(\frac{p}{q}) = (\frac{q}{p})$
- 如果 p ≡ q ≡ 3 (mod 4)，则 $(\frac{p}{q}) = -(\frac{q}{p})$
补充定律：
- $(\frac{-1}{p}) = (-1)^{\frac{p-1}{2}}$，即 -1 是模 p 的二次剩余当且仅当 p ≡ 1 (mod 4)
- $(\frac{2}{p}) = (-1)^{\frac{p^2-1}{8}}$，即 2 是模 p 的二次剩余当且仅当 p ≡ ±1 (mod 8)
示例：判断 7 是否是模 11 的二次剩余
使用二次互反律：
$(\frac{7}{11})(\frac{11}{7}) = (-1)^{3 \cdot 5} = -1$（因为 7 ≡ 3 mod 4, 11 ≡ 3 mod 4）
所以 $(\frac{7}{11}) = -(\frac{11}{7}) = -(\frac{4}{7})$（因为 11 ≡ 4 mod 7）
4 = 2²，所以 $(\frac{4}{7}) = 1$。
因此 $(\frac{7}{11}) = -1$，7 不是模 11 的二次剩余。
验证：1²=1, 2²=4, 3²=9, 4²=5, 5²=3 (mod 11)。确实没有平方等于 7。✓
雅可比符号
雅可比符号是勒让德符号的推广，允许分母为任意奇正整数：
$$\left(\frac{a}{n}\right) = \prod_{i=1}^{k} \left(\frac{a}{p_i}\right)^{e_i}$$
其中 $n = p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$ 是 n 的素因数分解。
雅可比符号保留了二次互反律的形式，但注意：$(\frac{a}{n}) = 1$ 并不意味着 a 是模 n 的二次剩余（只有当 n 是素数时才等价）。
4.4 数论函数
莫比乌斯函数
莫比乌斯函数 μ(n) 定义为：
$$\mu(n) = \begin{cases}
1 & \text{if } n = 1 \\
(-1)^k & \text{if } n \text{ 是 } k \text{ 个不同素数的乘积} \\
0 & \text{if } n \text{ 有平方因子}
\end{cases}$$
示例：
- μ(1) = 1
- μ(6) = μ(2×3) = (-1)² = 1
- μ(30) = μ(2×3×5) = (-1)³ = -1
- μ(12) = μ(2²×3) = 0（因为有平方因子 2²）
性质：
- μ 是积性函数：如果 gcd(m, n) = 1，则 μ(mn) = μ(m)μ(n)
- $\sum_{d|n} \mu(d) = \begin{cases} 1 & \text{if } n = 1 \\ 0 & \text{if } n > 1 \end{cases}$
证明第二个性质：如果 n > 1，设 $n = p_1^{e_1}\cdots p_k^{e_k}$。只有不含平方因子的 d 才对求和有贡献，这样的 d 必须是不同素数的乘积。有 $\binom{k}{j}$ 个由 j 个不同素数组成的 d，每个贡献 (-1)^j。所以 $\sum_{d|n} \mu(d) = \sum_{j=0}^{k} \binom{k}{j}(-1)^j = (1-1)^k = 0$。✓
莫比乌斯反演公式
定理（莫比乌斯反演）：设 f, g 是数论函数，满足：
$$g(n) = \sum_{d|n} f(d)$$
则：
$$f(n) = \sum_{d|n} \mu(d) g\left(\frac{n}{d}\right)$$
证明：
$$\sum_{d|n} \mu(d) g\left(\frac{n}{d}\right) = \sum_{d|n} \mu(d) \sum_{e|\frac{n}{d}} f(e) = \sum_{e|n} f(e) \sum_{d|\frac{n}{e}} \mu(d)$$
内部求和 $\sum_{d|\frac{n}{e}} \mu(d)$ 当 n/e = 1（即 e = n）时为 1，否则为 0。所以整个表达式等于 f(n)。✓
应用：莫比乌斯反演在组合数学和解析数论中有广泛应用，如计算欧拉函数、除数函数等。
示例：欧拉函数 φ(n) 可以用莫比乌斯反演表示。我们知道 $n = \sum_{d|n} \phi(d)$（因为 1 到 n 的整数按与 n 的最大公约数分类，每类的大小是 φ(n/d)）。由莫比乌斯反演：
$$\phi(n) = \sum_{d|n} \mu(d) \frac{n}{d} = n \sum_{d|n} \frac{\mu(d)}{d}$$
除数函数
除数函数 d(n)（或 τ(n)）定义为 n 的正因数个数。
计算公式：如果 $n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$，则：
$$d(n) = (e_1 + 1)(e_2 + 1)\cdots(e_k + 1)$$
示例：d(12) = d(2²×3) = (2+1)(1+1) = 6。12 的因数为 1, 2, 3, 4, 6, 12。✓
约数和函数 σ(n) 定义为 n 的所有正因数之和：
$$\sigma(n) = \sum_{d|n} d$$
计算公式：$\sigma(n) = \prod_{i=1}^{k} \frac{p_i^{e_i+1}-1}{p_i-1}$
完美数：如果 σ(n) = 2n（即除了 n 本身外的因数之和等于 n），则 n 是完美数。例如 6 = 1+2+3，28 = 1+2+4+7+14。
4.5 素性测试
试除法
最简单的素性测试：检查 2 到 √n 是否有因数。时间复杂度 O(√n)，对于大数太慢。
优化：只需检查 2 和奇数，或者只检查素数。
费马素性测试
基于费马小定理：如果 p 是素数，则 a^{p-1} ≡ 1 (mod p) 对所有 1 ≤ a < p 成立。
算法：随机选择 a，检查 a^{n-1} mod n 是否等于 1。如果不等于，n 一定是合数；如果等于，n 可能是素数。
问题：存在卡迈克尔数（Carmichael Numbers），如 561 = 3×11×17，对所有与 n 互质的 a 都满足 a^{n-1} ≡ 1 (mod n)，但 n 是合数。
卡迈克尔数的性质：
- 必须是奇数
- 必须是至少三个不同素数的乘积
- 对每个素因子 p，有 p-1 | n-1
Miller-Rabin 素性测试
Miller-Rabin 测试是目前最常用的概率素性测试：
原理：如果 n 是奇素数，则 n-1 = 2ˢ·d（d 是奇数）。对任意 a，要么 aᵈ ≡ 1 (mod n)，要么存在 r < s 使得 a^{2ʳᵈ} ≡ -1 (mod n)。
证明：由费马小定理，a^{n-1} = a^{2ˢᵈ} ≡ 1 (mod n)。所以 a^{2^{s-1}d} 是 1 的平方根 mod n。如果 n 是素数，1 的平方根只能是 ±1。如果 a^{2^{s-1}d} ≡ 1，继续往前推；如果 a^{2^{s-1}d} ≡ -1，停止。最终要么得到 aᵈ ≡ 1，要么在某一步得到 -1。
算法：
将 n-1 写成 2ˢ·d
随机选择 a ∈ [2, n-2]
计算 x = aᵈ mod n
如果 x = 1 或 x = n-1，通过本轮测试
否则，重复 s-1 次：x = x² mod n，如果 x = n-1，通过
如果以上都不满足，n 是合数
性质：如果 n 是合数，至少 3/4 的 a 能检测出 n 是合数。进行 k 轮测试，错误概率 ≤ (1/4)ᵏ。
import random
def miller_rabin(n, k=10):
"""Miller-Rabin 素性测试"""
if n < 2:
return False
if n == 2 or n == 3:
return True
if n % 2 == 0:
return False
# 将 n-1 写成 2^s * d
s, d = 0, n - 1
while d % 2 == 0:
s += 1
d //= 2
def check(a):
x = pow(a, d, n)
if x == 1 or x == n - 1:
return True
for _ in range(s - 1):
x = pow(x, 2, n)
if x == n - 1:
return True
return False
for _ in range(k):
a = random.randrange(2, n - 1)
if not check(a):
return False
return True
# 测试
for n in [2, 3, 17, 561, 1009, 1000000007]:
print(f"{n}: {'素数' if miller_rabin(n) else '合数'}")
# 561 是卡迈克尔数，费马测试会误判，但 Miller-Rabin 能正确识别
print(f"561 是卡迈克尔数: {miller_rabin(561)}") # 应该输出 FalseAKS 素性测试
AKS 测试（Agrawal-Kayal-Saxena）是第一个确定的多项式时间素性测试算法，发表于2002年。时间复杂度为 Õ((log n)^6)，但实际应用中 Miller-Rabin 更高效。
4.6 连分数
定义
连分数（Continued Fraction）是形如：
$$a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{a_3 + \cdots}}}$$
的表达式，简记为 [a₀; a₁, a₂, a₃, ...]。
如果连分数有限，记为 [a₀; a₁, a₂, ..., aₙ]；如果无限，表示一个无理数。
有理数的连分数展开
任何有理数都有有限的连分数展开。欧几里得算法本质上就是求连分数的过程。
算法：对于有理数 p/q：
a₀ = ⌊p/q⌋
如果余数为0，结束；否则，对 q/(p mod q) 递归执行
示例：22/7 的连分数展开
22/7 = 3 + 1/7 = [3; 7]示例：355/113 的连分数展开
355/113 = 3 + 16/113 = 3 + 1/(113/16) = 3 + 1/(7 + 1/16) = [3; 7, 16]无理数的连分数展开
无理数有无限的连分数展开。
示例：π ≈ [3; 7, 15, 1, 292, 1, 1, 1, 2, ...]
示例：黄金比例 φ = (1+√5)/2 = [1; 1, 1, 1, ...]（最"难"逼近的无理数）
示例：√2 = [1; 2, 2, 2, ...]（周期性连分数）
最佳有理逼近
连分数提供了无理数的最佳有理逼近。第 k 个渐近分数 pₖ/qₖ 满足：
$$\left|\alpha - \frac{p_k}{q_k}\right| < \frac{1}{q_k q_{k+1}} < \frac{1}{q_k^2}$$
例如，π 的连分数前几项给出：
- [3] = 3
- [3; 7] = 22/7 ≈ 3.142857
- [3; 7, 15] = 333/106 ≈ 3.141509
- [3; 7, 15, 1] = 355/113 ≈ 3.1415929
355/113 是 π 的一个极好的有理近似，误差小于 3×10⁻⁷。
渐近分数的递推计算
设连分数为 [a₀; a₁, a₂, ...]，渐近分数 pₖ/qₖ 满足：
- p₋₁ = 1, p₀ = a₀, pₖ = aₖpₖ₋₁ + pₖ₋₂
- q₋₁ = 0, q₀ = 1, qₖ = aₖqₖ₋₁ + qₖ₋₂
4.7 离散对数
定义
设 g 是模 p 的原根（即 g 的幂生成所有非零剩余类）。对任意 a ≢ 0 (mod p)，存在唯一的指数 x 使得 gˣ ≡ a (mod p)。这个 x 称为 a 以 g 为底的离散对数，记作 x = log_g(a) mod p。
困难性
离散对数问题（DLP）：给定 g, h, p，求 x 使得 gˣ ≡ h (mod p)。
目前没有已知的多项式时间算法。最好的通用算法（如指标演算法、数域筛法）的时间复杂度是亚指数的。
应用
- Diffie-Hellman 密钥交换：安全性基于 DLP 的困难性
- ElGamal 加密：公钥加密方案
- 数字签名算法（DSA）
三、程序员的视角
4.1 在密码学中的应用
- RSA加速：使用CRT将RSA解密速度提高约4倍。具体做法是将模数 n = pq 分解，分别在 mod p 和 mod q 下进行解密，然后用CRT合并。
- 椭圆曲线密码：基于有限域上的离散对数问题，但群运算是椭圆曲线上的点加法。相比传统离散对数，可以使用更短的密钥获得相同的安全性。
- Diffie-Hellman密钥交换：基于模幂运算。Alice 和 Bob 公开约定大素数 p 和原根 g。Alice 选择秘密 a，发送 gᵃ mod p；Bob 选择秘密 b，发送 gᵇ mod p。双方计算共享密钥 (gᵇ)ᵃ = (gᵃ)ᵇ = gᵃᵇ mod p。
- 数字签名：DSA 和 ECDSA 都依赖于离散对数问题。
4.2 常见陷阱
陷阱1：CRT的互质条件
CRT要求模数两两互质。如果不满足，需要先化简或使用广义CRT。例如，方程组 x ≡ 1 (mod 4), x ≡ 3 (mod 6) 不能直接用CRT，因为 gcd(4,6) = 2 ≠ 1。但可以检查相容性：1 ≡ 3 (mod 2) 成立，所以有解。化简后得到 x ≡ 1 (mod 4), x ≡ 3 (mod 3)，即 x ≡ 1 (mod 4), x ≡ 0 (mod 3)，解为 x ≡ 9 (mod 12)。
陷阱2：概率素性测试的错误
Miller-Rabin是概率算法，存在极小的错误概率。对于密码学应用，需要进行足够多轮测试（通常 k ≥ 40）。如果需要确定性结果，可以使用AKS测试或对特定范围的数使用预计算的伪素数表。
陷阱3：小素数攻击
在基于离散对数的密码系统中，如果选择的素数 p 使得 p-1 只有小素因子，则可以使用 Pohlig-Hellman 算法高效求解离散对数。应选择安全素数 p = 2q + 1，其中 q 也是素数。
4.3 与其他领域的联系
- 信号处理：FFT算法中使用单位根的性质，单位根是复数域中的"模幂"概念
- 计算机图形学：伪随机数生成使用线性同余发生器 X_{n+1} = (aXₙ + c) mod m
- 数据库：一致性哈希使用模运算将数据分布到多个节点
- 编译原理：哈希表的冲突解决使用模运算
四、代码实战
4.1 完整的数论高级工具库
class AdvancedNumberTheory:
"""高级数论工具"""
@staticmethod
def legendre_symbol(a, p):
"""计算勒让德符号 (a/p)"""
ls = pow(a, (p - 1) // 2, p)
return -1 if ls == p - 1 else ls
@staticmethod
def is_quadratic_residue(a, p):
"""判断a是否是模p的二次剩余"""
return AdvancedNumberTheory.legendre_symbol(a, p) == 1
@staticmethod
def mobius(n):
"""计算莫比乌斯函数"""
if n == 1:
return 1
factors = {}
d = 2
temp = n
while d * d <= temp:
while temp % d == 0:
factors[d] = factors.get(d, 0) + 1
if factors[d] > 1:
return 0 # 有平方因子
temp //= d
d += 1
if temp > 1:
factors[temp] = 1
return (-1) ** len(factors)
@staticmethod
def divisor_count(n):
"""计算除数函数 d(n)"""
count = 1
d = 2
temp = n
while d * d <= temp:
exp = 0
while temp % d == 0:
exp += 1
temp //= d
count *= (exp + 1)
d += 1
if temp > 1:
count *= 2
return count
@staticmethod
def divisor_sum(n):
"""计算约数和函数 sigma(n)"""
result = 1
d = 2
temp = n
while d * d <= temp:
if temp % d == 0:
exp = 0
while temp % d == 0:
exp += 1
temp //= d
result *= (d**(exp+1) - 1) // (d - 1)
d += 1
if temp > 1:
result *= (temp**2 - 1) // (temp - 1)
return result
@staticmethod
def continued_fraction(rational, max_terms=20):
"""有理数的连分数展开"""
num, den = rational
terms = []
for _ in range(max_terms):
if den == 0:
break
q = num // den
terms.append(q)
num, den = den, num - q * den
if den == 0:
break
return terms
@staticmethod
def convergents_from_cf(terms):
"""从连分数项计算渐近分数"""
convergents = []
h_prev, h_curr = 1, terms[0]
k_prev, k_curr = 0, 1
convergents.append((h_curr, k_curr))
for i in range(1, len(terms)):
h_next = terms[i] * h_curr + h_prev
k_next = terms[i] * k_curr + k_prev
convergents.append((h_next, k_next))
h_prev, h_curr = h_curr, h_next
k_prev, k_curr = k_curr, k_next
return convergents
@staticmethod
def euler_phi(n):
"""计算欧拉函数 phi(n)"""
result = n
d = 2
temp = n
while d * d <= temp:
if temp % d == 0:
while temp % d == 0:
temp //= d
result -= result // d
d += 1
if temp > 1:
result -= result // temp
return result
@staticmethod
def primitive_root(p):
"""寻找模p的最小原根（p为素数）"""
if p == 2:
return 1
phi_p = p - 1
# 找出 p-1 的所有素因子
factors = set()
temp = phi_p
d = 2
while d * d <= temp:
while temp % d == 0:
factors.add(d)
temp //= d
d += 1
if temp > 1:
factors.add(temp)
# 测试每个候选
for g in range(2, p):
is_primitive = True
for factor in factors:
if pow(g, phi_p // factor, p) == 1:
is_primitive = False
break
if is_primitive:
return g
return None
# 测试
ant = AdvancedNumberTheory()
print("=== 高级数论工具测试 ===")
print(f"(7/11) = {ant.legendre_symbol(7, 11)}")
print(f"7是模11的二次剩余吗？{ant.is_quadratic_residue(7, 11)}")
print(f"μ(30) = {ant.mobius(30)}")
print(f"d(12) = {ant.divisor_count(12)}")
print(f"σ(12) = {ant.divisor_sum(12)}")
print(f"22/7的连分数: {ant.continued_fraction((22, 7))}")
print(f"φ(12) = {ant.euler_phi(12)}")
print(f"模7的最小原根: {ant.primitive_root(7)}")4.2 RSA加密演示
def rsa_demo():
"""简单的RSA加密演示"""
import random
# 选择两个小素数（实际应用中需要大素数）
p, q = 61, 53
n = p * q
phi_n = (p - 1) * (q - 1)
# 选择公钥指数 e
e = 17
assert ant.gcd(e, phi_n) == 1
# 计算私钥指数 d（e 的逆元 mod phi_n）
def extended_gcd(a, b):
if b == 0:
return a, 1, 0
g, x1, y1 = extended_gcd(b, a % b)
return g, y1, x1 - (a // b) * y1
_, d, _ = extended_gcd(e, phi_n)
d = d % phi_n
print(f"公钥: (e={e}, n={n})")
print(f"私钥: (d={d}, n={n})")
# 加密
message = 42
ciphertext = pow(message, e, n)
print(f"明文: {message}")
print(f"密文: {ciphertext}")
# 解密
decrypted = pow(ciphertext, d, n)
print(f"解密: {decrypted}")
# 使用CRT加速解密
dp = d % (p - 1)
dq = d % (q - 1)
m1 = pow(ciphertext, dp, p)
m2 = pow(ciphertext, dq, q)
# CRT合并
q_inv = pow(q, -1, p)
m = (m2 + q * ((m1 - m2) * q_inv % p)) % n
print(f"CRT解密: {m}")
rsa_demo()五、深入思考
5.1 历史背景
中国剩余定理源自中国古代数学著作《孙子算经》（约公元3-5世纪）。二次互反律由高斯首次完整证明，他称之为"黄金定理"。莫比乌斯函数由德国天文学家莫比乌斯于1832年引入。费马小定理由皮埃尔·德·费马在1640年提出，但第一个证明由欧拉给出。
5.2 未解决的问题
黎曼假设：与素数分布密切相关，是千禧年大奖难题之一
二次剩余的分布：是否存在更高效的判定算法？
连分数的统计性质：典型无理数的连分数系数的分布规律
离散对数的复杂性：是否存在多项式时间算法？
卡迈克尔数的分布：有多少个卡迈克尔数小于 x？
5.3 延伸阅读
《数论导引》 - Hardy & Wright
《A Classical Introduction to Modern Number Theory》 - Ireland & Rosen
《具体数学》第4章 - Graham, Knuth, Patashnik
《An Introduction to Mathematical Cryptography》 - Hoffstein et al.
六、实验笔记
实验一：CRT在大数运算中的应用
目标：使用CRT加速大数乘法。
步骤：
选择一组两两互质的小模数 m₁, m₂, ..., mₖ
将大数 A 和 B 分别表示为模这些小模数的余数组
在余数域中进行乘法：Cᵢ = Aᵢ × Bᵢ mod mᵢ
使用CRT还原结果 C mod M，其中 M = m₁m₂...mₖ
比较直接乘法和CRT方法的时间
思考题：
- 如何选择模数以最大化加速效果？
- CRT方法的精度限制是什么？
实验二：Miller-Rabin测试的性能分析
目标：分析Miller-Rabin测试在不同轮数下的准确性。
步骤：
生成一批已知的素数和合数（可以使用 sympy 的 isprime 验证）
用不同轮数（k=1, 5, 10, 20, 40）的Miller-Rabin测试
统计误判率（将合数误判为素数的比例）
绘制误判率随 k 变化的曲线
思考题：
- 为什么误判率随 k 指数下降？
- 对于密码学应用，k 应该取多少？
实验三：连分数逼近无理数
目标：研究不同无理数的连分数展开特性。
步骤：
计算 π, e, √2, φ 的前50个连分数项
计算对应的渐近分数
分析逼近误差与分母大小的关系
观察哪些无理数有周期性连分数
七、本章小结
关键定理：
- 中国剩余定理：同余方程组的求解，要求模数两两互质
- 费马小定理：a^{p-1} ≡ 1 (mod p)，p 为素数
- 欧拉定理：a^{φ(n)} ≡ 1 (mod n)，gcd(a,n)=1
- 二次互反律：$(\frac{p}{q})(\frac{q}{p}) = (-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}$
- 莫比乌斯反演：从求和函数反演原函数
核心算法：
CRT构造算法：O(k log M) 时间
Miller-Rabin素性测试：O(k log² n) 时间，错误概率 ≤ (1/4)ᵏ
快速幂算法：O(log n) 次乘法
连分数展开：欧几里得算法的变种
扩展欧几里得算法：求逆元和贝祖系数
应用总结：
- 密码学：RSA、Diffie-Hellman、数字签名
- 算法优化：大数运算、并行计算
- 数值分析：无理数逼近、有理近似
八、习题
基础题
习题 4.1：使用CRT求解：x ≡ 1 (mod 2), x ≡ 2 (mod 3), x ≡ 3 (mod 5)。
提示：M = 30，分别计算 M₁=15, M₂=10, M₃=6 的逆元。
习题 4.2：计算 (15/23) 的值。
提示：使用二次互反律，注意 15 = 3×5。
习题 4.3：计算 μ(60) 和 d(60)。
提示：60 = 2²×3×5，注意平方因子。
习题 4.4：计算 φ(100)。
提示：100 = 2²×5²，使用公式 φ(n) = n∏(1-1/p)。
进阶题
习题 4.5：[ME] 证明：如果 p ≡ 1 (mod 4)，则 -1 是模 p 的二次剩余。
提示：使用欧拉判别准则，计算 (-1)^{(p-1)/2}。
习题 4.6：[ME] 使用莫比乌斯反演证明：$\phi(n) = \sum_{d|n} \mu(d) \frac{n}{d}$。
提示：首先证明 $n = \sum_{d|n} \phi(d)$，然后应用莫比乌斯反演。
习题 4.7：[ME] 证明：如果 n 是卡迈克尔数，则 n 是无平方因子的，且对每个素因子 p，有 p-1 | n-1。
提示：使用 Korselt 判别准则。
挑战题
习题 4.8：[HM25] 实现AKS素性测试算法的简化版本。
提示：AKS的核心是检查 (x+a)^n ≡ x^n + a (mod n, x^r-1) 是否成立。
习题 4.9：[HM30] 研究连分数在破解RSA中的应用（当私钥过小时）。
提示：Wiener攻击利用 e/n 的连分数展开来恢复小的私钥 d。
习题 4.10：[HM40] 证明二次互反律。
提示：可以使用高斯引理或 Eisenstein 的几何证明。高斯引理指出：$(\frac{a}{p}) = (-1)^\mu$，其中 μ 是集合 {a, 2a, ..., ((p-1)/2)a} 中大于 p/2 的元素个数。
本章完