数论基础

数论（Number Theory）是研究整数性质的数学分支，被誉为"数学皇后"。虽然数论曾被认为是纯数学中最不实用的分支，但随着现代密码学的发展，它成为网络安全的基石。RSA 加密、椭圆曲线加密等核心技术都建立在数论的基础之上。

整除性

整除的定义

设 $a$ 和 $b$ 是整数， $a \neq 0$ 。如果存在整数 $k$ 使得 $b = ak$ ，则称 $a$ 整除 $b$ ，记作 $a | b$ 。此时， $a$ 称为 $b$ 的因数（约数）， $b$ 称为 $a$ 的倍数。

如果 $a$ 不整除 $b$ ，记作 $a \nmid b$ 。

整除的性质

基本性质：

若 $a | b$ 且 $b | c$ ，则 $a | c$ （传递性）
若 $a | b$ 且 $a | c$ ，则 $a | (mb + nc)$ 对任意整数 $m, n$ 成立（线性组合）
若 $a | b$ 且 $b | a$ ，则 $a = b$ 或 $a = -b$
若 $a | b$ 且 $b \neq 0$ ，则 $|a| \leq |b|$

def divides(a, b):
    """检查 a 是否整除 b"""
    if a == 0:
        return b == 0
    return b % a == 0

def get_divisors(n):
    """获取 n 的所有正因数"""
    if n == 0:
        return []
    n = abs(n)
    divisors = []
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)
    return sorted(divisors)

print(get_divisors(12))  # [1, 2, 3, 4, 6, 12]

带余除法

定理（带余除法）：对于任意整数 $a$ 和正整数 $b$ ，存在唯一的整数 $q$ （商）和 $r$ （余数），使得：

$a = bq + r, \quad 0 \leq r < b$

这是整数除法的基础。余数记作 $a \bmod b$ 。

# Python 中的除法
# 注意：Python 的 % 运算符对负数的结果与数学定义一致
print(17 // 5, 17 % 5)   # 3 2
print(-17 // 5, -17 % 5) # -4 3 (因为 -17 = 5*(-4) + 3)

最大公约数与最小公倍数

最大公约数

设 $a$ 和 $b$ 是不全为零的整数。 $a$ 和 $b$ 的最大公约数（Greatest Common Divisor，GCD）是同时整除 $a$ 和 $b$ 的最大正整数，记作 $\gcd(a, b)$ 或 $(a, b)$ 。

性质：

$\gcd(a, b) = \gcd(b, a)$
$\gcd(a, 0) = |a|$
$\gcd(a, b) = \gcd(a - b, b)$ （辗转相减法的依据）
$\gcd(a, b) = \gcd(a \bmod b, b)$ （欧几里得算法的依据）

def gcd(a, b):
    """欧几里得算法求最大公约数"""
    a, b = abs(a), abs(b)
    while b:
        a, b = b, a % b
    return a

print(gcd(48, 18))  # 6
print(gcd(17, 13))  # 1（互质）

互质

如果 $\gcd(a, b) = 1$ ，则称 $a$ 和 $b$ 互质（或互素）。

重要性质：

若 $\gcd(a, b) = 1$ 且 $\gcd(a, c) = 1$ ，则 $\gcd(a, bc) = 1$
若 $a | bc$ 且 $\gcd(a, b) = 1$ ，则 $a | c$
若 $a | c$ ， $b | c$ 且 $\gcd(a, b) = 1$ ，则 $ab | c$

最小公倍数

$a$ 和 $b$ 的最小公倍数（Least Common Multiple，LCM）是同时被 $a$ 和 $b$ 整除的最小正整数，记作 $\text{lcm}(a, b)$ 或 $[a, b]$ 。

关系：

$\gcd(a, b) \times \text{lcm}(a, b) = |ab|$

这个公式将 GCD 和 LCM 联系起来，计算 LCM 只需先求 GCD。

def lcm(a, b):
    """最小公倍数"""
    if a == 0 or b == 0:
        return 0
    return abs(a * b) // gcd(a, b)

print(lcm(12, 18))  # 36

扩展欧几里得算法

Bezout 定理：对于不全为零的整数 $a$ 和 $b$ ，存在整数 $x$ 和 $y$ ，使得：

$ax + by = \gcd(a, b)$

扩展欧几里得算法不仅可以求 GCD，还能求出系数 $x$ 和 $y$ 。

def extended_gcd(a, b):
    """扩展欧几里得算法
    返回 (gcd, x, y) 使得 ax + by = gcd
    """
    if b == 0:
        return a, 1, 0
    
    g, x1, y1 = extended_gcd(b, a % b)
    x = y1
    y = x1 - (a // b) * y1
    
    return g, x, y

# 验证
a, b = 48, 18
g, x, y = extended_gcd(a, b)
print(f"{a}*{x} + {b}*{y} = {a*x + b*y} = gcd({a},{b}) = {g}")
# 48*1 + 18*-2 = 12 = gcd(48,18) = 6

应用：解线性同余方程、求模逆元。

模运算

同余的定义

设 $m$ 是正整数。如果整数 $a$ 和 $b$ 满足 $m | (a - b)$ ，则称 $a$ 和 $b$ 模 $m$ 同余，记作：

$a \equiv b \pmod{m}$

等价地说， $a$ 和 $b$ 除以 $m$ 的余数相同。

同余的性质

基本性质：

自反性： $a \equiv a \pmod{m}$
对称性：若 $a \equiv b \pmod{m}$ ，则 $b \equiv a \pmod{m}$
传递性：若 $a \equiv b \pmod{m}$ 且 $b \equiv c \pmod{m}$ ，则 $a \equiv c \pmod{m}$

运算性质：

若 $a \equiv b \pmod{m}$ 且 $c \equiv d \pmod{m}$ ，则：

$a + c \equiv b + d \pmod{m}$
$a - c \equiv b - d \pmod{m}$
$ac \equiv bd \pmod{m}$

注意：同余式一般不能直接约分。 $ac \equiv bc \pmod{m}$ 不能推出 $a \equiv b \pmod{m}$ ，正确的结论是 $a \equiv b \pmod{m/\gcd(c, m)}$ 。

模运算的应用

快速幂：计算 $a^n \bmod m$ ，使用二进制分解将时间复杂度从 $O(n)$ 降到 $O(\log n)$ 。

def mod_pow(base, exp, mod):
    """快速幂取模"""
    result = 1
    base = base % mod
    
    while exp > 0:
        if exp % 2 == 1:
            result = (result * base) % mod
        exp = exp // 2
        base = (base * base) % mod
    
    return result

print(mod_pow(2, 100, 17))  # 计算 2^100 mod 17

素数

素数的定义

大于 1 的正整数 $p$ 如果只有 1 和 $p$ 两个正因数，则称 $p$ 为素数（质数）。大于 1 的非素数称为合数。

注意：1 既不是素数也不是合数。

素数的性质

素数有无穷多个（欧几里得证明）：

假设素数有限，设为 $p_1, p_2, \ldots, p_n$ 。考虑 $N = p_1 p_2 \cdots p_n + 1$ 。 $N$ 不能被任何 $p_i$ 整除（余数都是 1），所以 $N$ 要么是素数，要么有不在列表中的素因子。矛盾。

算术基本定理：每个大于 1 的整数都可以唯一表示为素数的乘积（不计顺序）：

$n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$

其中 $p_1 < p_2 < \cdots < p_k$ 是素数， $a_i \geq 1$ 。

素数判定

朴素方法：检查从 2 到 $\sqrt{n}$ 是否有因数。

import math

def is_prime(n):
    """朴素素数判定"""
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        if n % i == 0:
            return False
    
    return True

Miller-Rabin 素性测试：一种概率性算法，可以快速判定大数是否为"可能的素数"。

素数筛法

埃拉托斯特尼筛法：找出不超过 $n$ 的所有素数。

def sieve_of_eratosthenes(n):
    """埃拉托斯特尼筛法"""
    if n < 2:
        return []
    
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    
    for i in range(2, int(n**0.5) + 1):
        if is_prime[i]:
            for j in range(i*i, n + 1, i):
                is_prime[j] = False
    
    return [i for i in range(n + 1) if is_prime[i]]

print(sieve_of_eratosthenes(30))
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

时间复杂度： $O(n \log \log n)$

威尔逊定理

威尔逊定理（Wilson's Theorem）提供了一个判定素数的充要条件，虽然在计算上不如其他方法高效，但在理论上有重要意义。

定理内容：对于大于 1 的整数 $n$ ， $n$ 是素数当且仅当：

$(n-1)! \equiv -1 \pmod{n}$

等价地说， $n$ 是素数当且仅当 $(n-1)! + 1$ 能被 $n$ 整除。

理解定理：阶乘 $(n-1)!$ 是 $1 \times 2 \times 3 \times \cdots \times (n-1)$ 。当 $n$ 是素数时，这些因子两两配对互为模 $n$ 的逆元，只剩下 $1$ 和 $n-1$ （即 $-1$ ）自逆，所以乘积为 $-1$ 。

证明思路（必要性）：

设 $p$ 是素数。在模 $p$ 下， $1, 2, \ldots, p-1$ 每个数都有唯一的乘法逆元。

$1$ 的逆元是 $1$ （自逆）
$p-1$ 的逆元是 $p-1$ （因为 $(p-1)^2 = p^2 - 2p + 1 \equiv 1 \pmod{p}$ ）
其余 $p-3$ 个数可以配对，每对的乘积为 $1$

因此：

$(p-1)! = 1 \times (p-1) \times (\text{配对数的乘积}) \equiv 1 \times (-1) \times 1 \times \cdots \times 1 \equiv -1 \pmod{p}$

例子：

$n = 5$ ： $(5-1)! = 24 = 5 \times 5 - 1 \equiv -1 \pmod{5}$ ✓
$n = 7$ ： $6! = 720 = 7 \times 103 - 1 \equiv -1 \pmod{7}$ ✓
$n = 4$ ： $3! = 6 \equiv 2 \not\equiv -1 \pmod{4}$ ，4 不是素数 ✓

def wilson_test(n):
    """用威尔逊定理判定素数（仅用于演示，不实用）"""
    if n <= 1:
        return False
    return math.factorial(n - 1) % n == n - 1

# 验证
for n in range(2, 15):
    print(f"{n}: {wilson_test(n)}")
# 2: True, 3: True, 4: False, 5: True, 6: False, 7: True, ...

局限性：威尔逊定理需要计算 $(n-1)!$ ，其增长速度极快，对于大数完全不实用。但它揭示了素数的一个深刻性质，在理论研究中很有价值。

模逆元

定义

设 $m$ 是正整数， $a$ 是整数。如果存在整数 $x$ 使得 $ax \equiv 1 \pmod{m}$ ，则称 $x$ 是 $a$ 模 $m$ 的逆元，记作 $a^{-1} \bmod m$ 。

存在性定理： $a$ 模 $m$ 的逆元存在当且仅当 $\gcd(a, m) = 1$ 。

求模逆元

使用扩展欧几里得算法：

def mod_inverse(a, m):
    """求 a 模 m 的逆元，若不存在返回 None"""
    g, x, _ = extended_gcd(a % m, m)
    
    if g != 1:
        return None  # 逆元不存在
    
    return x % m  # 确保结果为正

print(mod_inverse(3, 7))   # 5，因为 3*5 = 15 ≡ 1 (mod 7)
print(mod_inverse(2, 4))   # None，gcd(2,4) = 2 ≠ 1

应用

模逆元用于模运算中的"除法"：

$\frac{a}{b} \bmod m = a \cdot b^{-1} \bmod m$

前提是 $b$ 与 $m$ 互质。

欧拉定理与费马小定理

欧拉函数

欧拉函数 $\phi(n)$ 定义为小于 $n$ 且与 $n$ 互质的正整数个数。

计算公式：若 $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$ ，则：

$\phi(n) = n \prod_{p|n} \left(1 - \frac{1}{p}\right) = n \cdot \left(1 - \frac{1}{p_1}\right)\left(1 - \frac{1}{p_2}\right) \cdots \left(1 - \frac{1}{p_k}\right)$

特殊值：

$\phi(p) = p - 1$ （ $p$ 是素数）
$\phi(p^k) = p^k - p^{k-1}$
若 $\gcd(m, n) = 1$ ，则 $\phi(mn) = \phi(m)\phi(n)$

def euler_phi(n):
    """计算欧拉函数值"""
    result = n
    p = 2
    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
    return result

print(euler_phi(12))  # 4，因为 1, 5, 7, 11 与 12 互质

欧拉定理

若 $\gcd(a, n) = 1$ ，则：

$a^{\phi(n)} \equiv 1 \pmod{n}$

应用：简化大指数模运算。例如，计算 $7^{100} \bmod 20$ ：

$\phi(20) = \phi(4 \times 5) = \phi(4) \times \phi(5) = 2 \times 4 = 8$

$7^8 \equiv 1 \pmod{20}$

$7^{100} = 7^{12 \times 8 + 4} = (7^8)^{12} \times 7^4 \equiv 1^{12} \times 7^4 = 2401 \equiv 1 \pmod{20}$

费马小定理

费马小定理是欧拉定理的特例。若 $p$ 是素数且 $\gcd(a, p) = 1$ ，则：

$a^{p-1} \equiv 1 \pmod{p}$

或等价地：

$a^p \equiv a \pmod{p}$

应用：

素性测试（Fermat 素性测试）
求模逆元：若 $p$ 是素数，则 $a^{-1} \equiv a^{p-2} \pmod{p}$

def fermat_inverse(a, p):
    """用费马小定理求逆元（p 是素数）"""
    return mod_pow(a, p - 2, p)

print(fermat_inverse(3, 7))  # 5

中国剩余定理

定理内容

设 $m_1, m_2, \ldots, m_k$ 两两互质，则同余方程组：

$\begin{cases} x \equiv a_1 \pmod{m_1} \\ x \equiv a_2 \pmod{m_2} \\ \vdots \\ x \equiv a_k \pmod{m_k} \end{cases}$

在模 $M = m_1 m_2 \cdots m_k$ 下有唯一解。

解法：

设 $M_i = M / m_i$ ， $M_i^{-1}$ 是 $M_i$ 模 $m_i$ 的逆元，则：

$x \equiv \sum_{i=1}^{k} a_i M_i M_i^{-1} \pmod{M}$

def chinese_remainder_theorem(remainders, moduli):
    """中国剩余定理求解
    remainders: [a1, a2, ..., ak]
    moduli: [m1, m2, ..., mk]，要求两两互质
    """
    M = 1
    for m in moduli:
        M *= m
    
    result = 0
    for a, m in zip(remainders, moduli):
        Mi = M // m
        Mi_inv = mod_inverse(Mi, m)
        result += a * Mi * Mi_inv
    
    return result % M

# 解 x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7)
x = chinese_remainder_theorem([2, 3, 2], [3, 5, 7])
print(x)  # 23
# 验证: 23 % 3 = 2, 23 % 5 = 3, 23 % 7 = 2

应用

中国剩余定理常用于将大数模运算分解为多个小数模运算，提高计算效率。

RSA 加密简介

RSA 是最广泛使用的非对称加密算法，其安全性基于大整数分解的困难性。

密钥生成

选择两个大素数 $p$ 和 $q$
计算 $n = pq$ 和 $\phi(n) = (p-1)(q-1)$
选择加密指数 $e$ ，满足 $1 < e < \phi(n)$ 且 $\gcd(e, \phi(n)) = 1$
计算解密指数 $d$ ，满足 $ed \equiv 1 \pmod{\phi(n)}$

公钥是 $(n, e)$ ，私钥是 $(n, d)$ 。

加密与解密

加密：密文 $c = m^e \bmod n$

解密：明文 $m = c^d \bmod n$

def rsa_keygen(p, q, e=65537):
    """RSA 密钥生成"""
    n = p * q
    phi_n = (p - 1) * (q - 1)
    d = mod_inverse(e, phi_n)
    return (n, e), (n, d)  # 公钥, 私钥

def rsa_encrypt(message, public_key):
    """RSA 加密"""
    n, e = public_key
    return mod_pow(message, e, n)

def rsa_decrypt(ciphertext, private_key):
    """RSA 解密"""
    n, d = private_key
    return mod_pow(ciphertext, d, n)

# 示例（使用小素数，实际应用需要大素数）
p, q = 61, 53
public_key, private_key = rsa_keygen(p, q)

message = 42
encrypted = rsa_encrypt(message, public_key)
decrypted = rsa_decrypt(encrypted, private_key)

print(f"原文: {message}, 加密: {encrypted}, 解密: {decrypted}")
# 原文: 42, 加密: 2557, 解密: 42

RSA 的安全性依赖于：已知 $n$ 和 $e$ ，难以计算出 $d$ 。而计算 $d$ 需要知道 $\phi(n)$ ，这需要分解 $n$ 得到 $p$ 和 $q$ 。对于足够大的 $n$ ，目前没有有效的分解算法。

安全性要求

密钥长度：RSA 的安全性依赖于大整数分解的困难性。目前推荐的最小密钥长度：

密钥长度	安全等级	备注
1024 位	不安全	已可被破解
2048 位	安全	当前标准
4096 位	高安全	用于敏感数据

素数选择要求：

$p$ 和 $q$ 应该长度相近
$p-1$ 和 $q-1$ 应有大素因子（防止 Pollard's $p-1$ 攻击）
$p$ 和 $q$ 的差应足够大（防止 Fermat 分解法）
使用强素数生成器

实际应用注意事项

教材 RSA vs 实际 RSA：上面展示的是"教材 RSA"（Textbook RSA），在实际应用中存在安全问题：

确定性问题：相同的明文总是加密成相同的密文，容易被统计分析
可乘性： $E(m_1) \times E(m_2) = E(m_1 \times m_2)$ ，可能被利用
小指数攻击：当明文很小且使用小公钥指数时可能被破解

填充方案：实际应用中使用填充方案解决这些问题。常用的有：

PKCS#1 v1.5：较早的填充方案，仍有使用
OAEP（Optimal Asymmetric Encryption Padding）：目前推荐的填充方案，提供可证明安全性

# 注意：实际应用应使用成熟的密码库，不要自己实现
# Python 示例：使用 cryptography 库
from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.hazmat.primitives import hashes

# 生成密钥
private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
public_key = private_key.public_key()

# 加密（使用 OAEP 填充）
message = b"Hello, RSA!"
ciphertext = public_key.encrypt(
    message,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None
    )
)

# 解密
plaintext = private_key.decrypt(
    ciphertext,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None
    )
)

混合加密：由于 RSA 加密速度慢，实际应用中通常使用混合加密：

生成一个随机的对称密钥（如 AES-256）
用对称密钥加密消息（快速）
用 RSA 加密对称密钥（安全传输）
将加密的对称密钥和加密消息一起发送

这种方式结合了对称加密的高效和非对称加密的密钥分发便利。

小结

本章介绍了数论的基础知识：

整除性：整除的定义与性质、带余除法
最大公约数与最小公倍数：欧几里得算法、扩展欧几里得算法、Bezout 定理
模运算：同余的定义与性质、快速幂
素数：定义与性质、素数判定、筛法、威尔逊定理
模逆元：定义、存在性、求法
欧拉定理与费马小定理：欧拉函数、欧拉定理、费马小定理
中国剩余定理：同余方程组的求解
RSA 加密：原理、实现、安全性要求与实际应用

数论是现代密码学的理论基础。理解模运算、欧拉定理和 RSA 的原理，有助于深入理解网络安全和数据保护的核心技术。

练习

用欧几里得算法计算 $\gcd(252, 105)$ ，并用扩展欧几里得算法找出 $x$ 和 $y$ 使得 $252x + 105y = \gcd(252, 105)$ 。
证明：如果 $p$ 是素数且 $p \nmid a$ ，则 $a^{-1} \equiv a^{p-2} \pmod{p}$ 。
使用中国剩余定理解同余方程组：
- $x \equiv 1 \pmod{3}$
- $x \equiv 2 \pmod{5}$
- $x \equiv 3 \pmod{7}$
计算 $\phi(1000)$ 。
用威尔逊定理验证 11 是否为素数，并解释为什么威尔逊定理不适合用于实际的大数素性测试。
解释为什么 RSA 中 $n$ 的分解等价于求出私钥 $d$ 。

整除性​

整除的定义​

整除的性质​

带余除法​

最大公约数与最小公倍数​

最大公约数​

互质​

最小公倍数​

扩展欧几里得算法​

模运算​

同余的定义​

同余的性质​

模运算的应用​

素数​

素数的定义​

素数的性质​

素数判定​

素数筛法​

威尔逊定理​

模逆元​

定义​

求模逆元​

应用​

欧拉定理与费马小定理​

欧拉函数​

欧拉定理​

费马小定理​

中国剩余定理​

定理内容​

应用​

RSA 加密简介​

密钥生成​

加密与解密​

安全性要求​

实际应用注意事项​

小结​

练习​

整除性