第五十七 数论
数论（Number Theory）是纯粹数学的一个分支，研究整数的性质和关系。它曾被高斯誉为“数学的女王“，长期被视为最纯粹、最远离应用的数学分支。然而，随着计算机科学和密码学的发展，数论在现代社会中找到了极其重要的应用——RSA 加密、椭圆曲线签名、区块链挖矿等技术的数学根基都来自数论。
一、整除与因数
1.1 整除的定义
若整数 $a$ 能被整数 $b$（$b \neq 0$）整除，即存在整数 $q$ 使得 $a = bq$，则记作 $b \mid a$，读作“$b$ 整除 $a$“。
1.2 最大公约数（GCD）
两个整数 $a$ 和 $b$ 的最大公约数 $\gcd(a, b)$ 是能同时整除两者的最大正整数。
**辗转相除法（欧几里得算法）**是求 GCD 的经典方法，时间复杂度 $O(\log(\min(a,b)))$：
#![allow(unused)]
fn main() {
fn gcd(mut a: u64, mut b: u64) -> u64 {
while b != 0 {
let r = a % b;
a = b;
b = r;
}
a
}
}最小公倍数（LCM）：
$$\text{lcm}(a, b) = \frac{a \cdot b}{\gcd(a, b)}$$
#![allow(unused)]
fn main() {
fn lcm(a: u64, b: u64) -> u64 {
a / gcd(a, b) * b // 先除后乘避免溢出
}
}1.3 扩展欧几里得算法
求整数 $x, y$ 使得 $ax + by = \gcd(a, b)$（贝祖等式）。这是求解模逆元的基础。
#![allow(unused)]
fn main() {
/// 返回 (gcd, x, y) 使得 a*x + b*y = gcd
fn ext_gcd(a: i64, b: i64) -> (i64, i64, i64) {
if b == 0 {
return (a, 1, 0);
}
let (g, x1, y1) = ext_gcd(b, a % b);
(g, y1, x1 - (a / b) * y1)
}
}二、素数
2.1 素数的定义
大于 1 的自然数，除了 1 和自身外没有其他正因数的数称为素数（质数）。前几个素数：2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, …
2 是唯一的偶素数。
2.2 素数判定
试除法（适用于小数）：只需检查到 $\sqrt{n}$。
#![allow(unused)]
fn main() {
fn is_prime(n: u64) -> bool {
if n < 2 { return false; }
if n < 4 { return true; }
if n % 2 == 0 || n % 3 == 0 { return false; }
let mut i = 5u64;
while i * i <= n {
if n % i == 0 || n % (i + 2) == 0 {
return false;
}
i += 6;
}
true
}
}Miller-Rabin 素性测试（适用于大数，概率性判定）：
对于密码学中 2048 位的大素数，需要高效的素性测试算法。Miller-Rabin 测试在 $k$ 轮测试下，错误概率不超过 $4^{-k}$。
2.3 埃拉托斯特尼筛法
筛法是批量求素数的经典算法。求 $n$ 以内所有素数：
#![allow(unused)]
fn main() {
fn sieve_of_eratosthenes(n: usize) -> Vec<usize> {
let mut is_prime = vec![true; n + 1];
is_prime[0] = false;
if n >= 1 { is_prime[1] = false; }
let mut i = 2;
while i * i <= n {
if is_prime[i] {
let mut j = i * i;
while j <= n {
is_prime[j] = false;
j += i;
}
}
i += 1;
}
is_prime.iter()
.enumerate()
.filter(|(_, &p)| p)
.map(|(i, _)| i)
.collect()
}
}时间复杂度 $O(n \log \log n)$，空间复杂度 $O(n)$。
2.4 素数定理
不超过 $x$ 的素数个数 $\pi(x)$ 渐近于：
$$\pi(x) \sim \frac{x}{\ln x}$$
| $x$ | $\pi(x)$ | $x / \ln x$（近似） |
|---|---|---|
| $10^2$ | 25 | 21.7 |
| $10^4$ | 1,229 | 1,085.7 |
| $10^6$ | 78,498 | 72,382.4 |
| $10^8$ | 5,761,455 | 5,428,681.0 |
2.5 孪生素数猜想
相差为 2 的素数对 $(p, p+2)$ 称为孪生素数，如 (3,5)、(11,13)、(17,19)。孪生素数是否有无穷多对至今未被证明。2013 年张益唐证明了存在无穷多对差小于 7000 万的素数对，此后该界被逐步缩小到 246。
三、同余与模运算
3.1 同余的定义
若 $a - b$ 能被 $m$ 整除，则称 $a$ 与 $b$ 模 $m$ 同余，记作：
$$a \equiv b \pmod{m}$$
3.2 模运算性质
| 性质 | 公式 |
|---|---|
| 加法 | $(a + b) \bmod m = [(a \bmod m) + (b \bmod m)] \bmod m$ |
| 乘法 | $(a \cdot b) \bmod m = [(a \bmod m) \cdot (b \bmod m)] \bmod m$ |
| 幂运算 | 可结合快速幂在 $O(\log n)$ 时间内计算 $a^n \bmod m$ |
3.3 快速幂（模幂运算）
计算 $a^b \bmod m$，RSA 加解密的核心操作：
#![allow(unused)]
fn main() {
fn mod_pow(mut base: u64, mut exp: u64, modulus: u64) -> u64 {
let mut result = 1u64;
base %= modulus;
while exp > 0 {
if exp % 2 == 1 {
result = result * base % modulus;
}
exp /= 2;
base = base * base % modulus;
}
result
}
}3.4 模逆元
$a$ 模 $m$ 的逆元 $a^{-1}$ 满足 $a \cdot a^{-1} \equiv 1 \pmod{m}$，当且仅当 $\gcd(a, m) = 1$ 时存在。
用扩展欧几里得算法求解：
#![allow(unused)]
fn main() {
fn mod_inverse(a: i64, m: i64) -> Option<i64> {
let (g, x, _) = ext_gcd(a, m);
if g != 1 {
None // 逆元不存在
} else {
Some(((x % m) + m) % m)
}
}
}四、重要定理
4.1 费马小定理
若 $p$ 是素数且 $\gcd(a, p) = 1$，则：
$$a^{p-1} \equiv 1 \pmod{p}$$
推论（模逆元）： $a^{-1} \equiv a^{p-2} \pmod{p}$，可用快速幂计算。
4.2 欧拉定理
费马小定理的推广。若 $\gcd(a, m) = 1$，则：
$$a^{\varphi(m)} \equiv 1 \pmod{m}$$
其中 $\varphi(m)$ 是欧拉函数，表示 $1$ 到 $m-1$ 中与 $m$ 互质的正整数个数。
| $m$ | $\varphi(m)$ | 与 $m$ 互质的数 |
|—–|———––|––––––––|
| 6 | 2 | 1, 5 |
| 8 | 4 | 1, 3, 5, 7 |
| 10 | 4 | 1, 3, 7, 9 |
| 12 | 4 | 1, 5, 7, 11 |
欧拉函数的计算：
若 $m = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$，则：
$$\varphi(m) = m \prod_{i=1}^{k} \left(1 - \frac{1}{p_i}\right)$$
#![allow(unused)]
fn main() {
fn euler_totient(mut n: u64) -> u64 {
let mut result = n;
let mut p = 2u64;
while p * p <= n {
if n % p == 0 {
while n % p == 0 {
n /= p;
}
result -= result / p;
}
p += 1;
}
if n > 1 {
result -= result / n;
}
result
}
}4.3 中国剩余定理
设 $m_1, m_2, \ldots, m_k$ 两两互质，则同余方程组
$$x \equiv a_i \pmod{m_i} \quad (i = 1, 2, \ldots, k)$$
在模 $M = m_1 m_2 \cdots m_k$ 下有唯一解。
4.4 威尔逊定理
$p$ 是素数当且仅当：
$$(p-1)! \equiv -1 \pmod{p}$$
五、数论在密码学中的应用
5.1 RSA 算法的数论基础
RSA 的安全性基于大整数分解困难问题：
| 步骤 | 数学描述 |
|---|---|
| 密钥生成 | 选两个大素数 $p, q$，计算 $n = pq$，$\varphi(n) = (p-1)(q-1)$ |
| 公钥 | $(n, e)$，其中 $\gcd(e, \varphi(n)) = 1$ |
| 私钥 | $d = e^{-1} \bmod \varphi(n)$ |
| 加密 | $c = m^e \bmod n$ |
| 解密 | $m = c^d \bmod n$ |
正确性由欧拉定理保证：$c^d = m^{ed} \equiv m \pmod{n}$。
5.2 离散对数问题
给定 $g, h, p$，求 $x$ 使得 $g^x \equiv h \pmod{p}$。
这在大素数下被认为是困难问题，是 Diffie-Hellman 密钥交换和 DSA 签名的安全基础。
5.3 椭圆曲线
椭圆曲线密码学（ECC）基于椭圆曲线上的离散对数困难问题。相比 RSA，ECC 在相同安全强度下使用更短的密钥：
| 安全等级 | RSA 密钥长度 | ECC 密钥长度 |
|---|---|---|
| 128 bit | 3072 bit | 256 bit |
| 256 bit | 15360 bit | 512 bit |
六、经典数论问题
6.1 哥德巴赫猜想
任何大于 2 的偶数都可以表示为两个素数之和。例如：$4 = 2+2$，$10 = 3+7 = 5+5$。至今未被证明。1966 年陈景润证明了每个充分大的偶数可表示为一个素数与一个至多两个素数之积的和（1+2）。
6.2 完美数
等于其所有真因数之和的数称为完美数。$6 = 1+2+3$，$28 = 1+2+4+7+14$。
欧拉证明：偶完美数与梅森素数 $M_p = 2^p - 1$ 一一对应，形式为 $2^{p-1}(2^p - 1)$。
是否存在奇完美数？是否存在无穷多完美数？均未解决。
6.3 费马大定理
方程 $x^n + y^n = z^n$ 在 $n \geq 3$ 时没有正整数解。费马在 1637 年声称有证明但未留下，1995 年安德鲁·怀尔斯最终证明。
6.4 黎曼猜想
黎曼 ζ 函数 $\zeta(s) = \sum_{n=1}^{\infty} \frac{1}{n^s}$ 的所有非平凡零点的实部都是 $\frac{1}{2}$。
这是数论最重要的未解决问题，与素数分布密切相关，也是千禧年七大数学难题之一。
七、总结与练习
本章小结
| 知识点 | 要点 |
|---|---|
| GCD 与 LCM | 欧几里得算法 $O(\log n)$ 求最大公约数 |
| 扩展欧几里得 | 求解贝祖等式，计算模逆元 |
| 素数判定 | 试除法 $O(\sqrt{n})$、Miller-Rabin 概率测试 |
| 埃氏筛法 | $O(n \log \log n)$ 批量求素数 |
| 快速幂 | $O(\log n)$ 计算 $a^b \bmod m$，密码学核心运算 |
| 费马小定理 / 欧拉定理 | 模运算中幂的核心恒等式 |
| 欧拉函数 | $\varphi(m)$ 与 RSA 密钥生成直接相关 |
| 中国剩余定理 | 同余方程组的求解 |
| 密码学应用 | RSA（大数分解）、DH（离散对数）、ECC（椭圆曲线） |
练习建议
- 素数筛法对比：分别实现埃氏筛法和线性筛法，比较求 $10^7$ 以内素数的性能。
- RSA 模拟：选取两个较小的素数，手动完成 RSA 密钥生成、加密、解密全过程，验证欧拉定理的正确性。
- 模逆元计算器：实现一个支持求模逆元的工具函数，处理逆元不存在的情况。
- 大数快速幂：实现支持 128 位整数的模幂运算，测试计算 $2^{1000000} \bmod (10^9+7)$。
- 欧拉函数表：用筛法预处理 $1$ 到 $n$ 的所有 $\varphi$ 值，时间复杂度 $O(n)$。
- 密码学思考：分析为什么 RSA 选择 $e = 65537$ 作为公钥指数，而非 $e = 3$ 或更大的值。