有限域 — 从 F_p 到 F_{p^n} 与扩域算术

日期: 2026-10-30 方向: 密码学数学 阶段: Phase 4 - 密码学数学基础 (Day 181-194) 标签: #密码学 #数学 #有限域 #扩域 #不可约多项式

---

今日目标

---

一、动机：为什么需要扩域？

核心：椭圆曲线的 pairing $e: \mathbb{G}_1 \times \mathbb{G}_2 \to \mathbb{G}T$ 中 $\mathbb{G}T \subset \mathbb{F}{p^k}^*$，$k$ 是嵌入度。BLS12-381 嵌入度 12，必须在 $\mathbb{F}{p^{12}}$ 上做最终幂。

---

二、严格定义

2.1 域 (Field)

定义 2.1：集合 $F$ 配两个运算 $(+, \cdot)$ 是域，若：

1. $(F, +)$ 是 abelian 群（单位元 0）
2. $(F \setminus {0}, \cdot)$ 是 abelian 群（单位元 1）
3. 分配律：$a(b+c) = ab + ac$

例子：$\mathbb{Q}, \mathbb{R}, \mathbb{C}, \mathbb{F}_p$。

2.2 有限域存在性

定理 2.2 (Galois)：阶为 $q$ 的有限域存在 $\Leftrightarrow q = p^n$，$p$ 素数，$n \ge 1$。且同构意义下唯一，记 $\mathbb{F}_q$ 或 $GF(q)$。

重要推论：不存在 6 元、10 元、12 元域；但存在 4 元 ($\mathbb{F}_{2^2}$)、8 元、9 元、27 元域。

2.3 特征 (Characteristic)

定义 2.3：$\text{char}(F) = $ 最小正整数 $n$ 使 $\underbrace{1+1+\dots+1}_n = 0$；若不存在则为 0。

定理 2.4：有限域特征必为素数 $p$。

2.4 素域 $\mathbb{F}_p$

最简单的有限域：$\mathbb{F}_p = \mathbb{Z}/p\mathbb{Z}$，$p$ 素数。运算就是模 $p$ 算术。

2.5 扩域 $\mathbb{F}_{p^n}$

定义 2.5：$\mathbb{F}_{p^n} = \mathbb{F}_p[x] / \langle f(x) \rangle$，其中 $f(x)$ 是 $\mathbb{F}_p$ 上 $n$ 次不可约多项式。

直觉：

• $\mathbb{F}_p[x]$ 是 $\mathbb{F}_p$ 系数的多项式环
• 商环 $/\langle f \rangle$ 表示「把 $f(x)$ 视为 0」
• 若 $f$ 不可约，则商环是域；若 $f$ 可约，会有零因子（不是域）

类比：$\mathbb{C} = \mathbb{R}[x]/\langle x^2+1 \rangle$，因为 $x^2+1$ 在 $\mathbb{R}$ 上不可约。

2.6 Frobenius 自同构

定理 2.6：在 $\mathbb{F}_{p^n}$ 上，映射 $\phi(x) = x^p$ 是域自同构（保持加法和乘法）。

Frobenius 的关键性质：$(a+b)^p = a^p + b^p$（特征 $p$ 的"frosh dream"），因为二项式系数 $\binom{p}{k}$ 对 $0 < k < p$ 都被 $p$ 整除。

用途：椭圆曲线点数计数 (Schoof's algorithm) 严重依赖 Frobenius 的迹。

2.7 乘法群结构

定理 2.7：$\mathbb{F}_q^* = \mathbb{F}_q \setminus {0}$ 是 $q-1$ 阶循环群。

意义：DLP 在 $\mathbb{F}_q^*$ 中可定义；找到生成元后所有元素都是 $g^k$ 形式。

---

三、完整推导

3.1 证明：$\mathbb{Z}/n\mathbb{Z}$ 是域 $\Leftrightarrow$ $n$ 素数

($\Rightarrow$)：若 $n=ab, 1<a,b<n$，则 $a, b$ 是非零零因子（$ab \equiv 0$），违反域的定义。

($\Leftarrow$)：若 $n=p$ 素数，前一节已证 $(\mathbb{Z}/p\mathbb{Z})^*$ 是群，加法群也满足，分配律继承自整数。$\blacksquare$

3.2 构造 $\mathbb{F}_4 = \mathbb{F}_2[x]/\langle x^2+x+1\rangle$

$\mathbb{F}_2 = {0, 1}$ 上 2 次多项式：

• $x^2$（可约 = $x \cdot x$）
• $x^2 + 1 = (x+1)^2$（可约）
• $x^2 + x = x(x+1)$（可约）
• $x^2 + x + 1$（不可约：代入 0, 1 都不为 0）

所以 $\mathbb{F}_4 = {0, 1, x, x+1}$，运算 mod $x^2+x+1$。验证：

• $x \cdot x = x^2 = -x-1 = x+1$（特征 2 中 $-1=1$）
• $x \cdot (x+1) = x^2+x = -1 = 1$，所以 $x^{-1} = x+1$

3.3 证明 $\mathbb{F}_q^*$ 循环

思路 (Gauss)：设 $|G|=q-1$。对每个 $d \mid q-1$，方程 $x^d = 1$ 在域上至多有 $d$ 个根（因多项式 $x^d-1$ 至多 $d$ 个根）。设 $N(d)$ 是阶恰为 $d$ 的元素数。则 $\sum_{d|q-1} N(d) = q-1$，且 Mobius 反演可证 $N(d) = \varphi(d)$ 当 $d \mid q-1$。特别 $N(q-1) = \varphi(q-1) > 0$，所以存在生成元。$\blacksquare$

3.4 Frobenius 推导

$$\phi(a+b) = (a+b)^p = \sum_{k=0}^p \binom{p}{k} a^{p-k} b^k$$

$\binom{p}{k} = \frac{p!}{k!(p-k)!}$。当 $0<k<p$，分子有 $p$ 但分母没有，所以 $p \mid \binom{p}{k}$。在特征 $p$ 中这些项为 0，剩 $a^p + b^p$。$\blacksquare$

---

四、直觉与图像

4.1 类比：扩域像「添加新数」

• $\mathbb{R} \to \mathbb{C}$：添加 $i$ 满足 $i^2 = -1$
• $\mathbb{F}_2 \to \mathbb{F}_4$：添加 $\alpha$ 满足 $\alpha^2 + \alpha + 1 = 0$
• $\mathbb{F}p \to \mathbb{F}{p^2}$：添加 $u$ 满足某二次不可约关系

每个 $\mathbb{F}{p^2}$ 元素可写成 $a + bu$（线性表示）；$\mathbb{F}{p^n}$ 是 $n$ 维 $\mathbb{F}_p$-向量空间。

4.2 塔结构 (Tower)

BLS12-381 用塔分解 $\mathbb{F}_{p^{12}}$：

F_p
 ↓ x: u² = -1
F_{p²} = F_p[u]/(u²+1)
 ↓ x: v³ = u + 1
F_{p⁶} = F_{p²}[v]/(v³ - (u+1))
 ↓ x: w² = v
F_{p^{12}} = F_{p⁶}[w]/(w² - v)

为什么塔：高效实现。$\mathbb{F}_{p^{12}}$ 上的乘法直接做需要 12×12=144 次小乘；用塔可压到 ~54 次。

---

五、代码实现 (finite_field.py)

"""
Day 182: 有限域 F_p 与扩域 F_{p^2}
完整实现 add/sub/mul/inv/pow
"""
from __future__ import annotations
from dataclasses import dataclass


# ============ F_p 素域 ============
class Fp:
    """素域 F_p 元素"""
    p: int  # 由子类设置

    def __init__(self, value: int):
        self.value = value % self.p

    def __add__(self, other): return type(self)((self.value + other.value) % self.p)
    def __sub__(self, other): return type(self)((self.value - other.value) % self.p)
    def __mul__(self, other): return type(self)((self.value * other.value) % self.p)
    def __neg__(self):        return type(self)((-self.value) % self.p)
    def __eq__(self, other):  return isinstance(other, Fp) and self.value == other.value and self.p == other.p
    def __repr__(self):       return f"Fp_{self.p}({self.value})"
    def __hash__(self):       return hash((self.value, self.p))

    def inv(self):
        """乘法逆元: 扩展欧几里得"""
        if self.value == 0:
            raise ZeroDivisionError("0 has no inverse in F_p")
        g, x, _ = extended_gcd(self.value, self.p)
        if g != 1:
            raise ValueError(f"{self.value} not coprime to {self.p}")
        return type(self)(x % self.p)

    def __truediv__(self, other): return self * other.inv()

    def pow(self, k: int):
        """快速幂 a^k mod p"""
        return type(self)(pow(self.value, k, self.p))

    def __pow__(self, k: int): return self.pow(k)


def extended_gcd(a: int, b: int) -> tuple[int, int, int]:
    """返回 (g, x, y) 使 ax + by = g = 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 make_fp(prime: int):
    """工厂: 创建 F_p 类"""
    class FpClass(Fp):
        p = prime
    FpClass.__name__ = f"Fp{prime}"
    return FpClass


# ============ F_{p^2} 扩域 ============
# 用 F_p[u] / (u² - β), β 是 F_p 中非二次剩余 (NQR)
@dataclass
class Fp2:
    """F_{p^2} = F_p[u] / (u² - beta)
    元素 a + b*u 用 (a, b) 表示
    """
    a: Fp  # 实部
    b: Fp  # 虚部 (u 系数)
    beta: int = -1  # u² = beta. 默认 -1 (类似 i)

    def __post_init__(self):
        # 校验 beta 是 NQR (此处简化, 假设调用方保证)
        pass

    def __add__(self, o): return Fp2(self.a + o.a, self.b + o.b, self.beta)
    def __sub__(self, o): return Fp2(self.a - o.a, self.b - o.b, self.beta)
    def __neg__(self):    return Fp2(-self.a, -self.b, self.beta)

    def __mul__(self, o):
        # (a + bu)(c + du) = (ac + bd·beta) + (ad + bc)u
        a, b, c, d = self.a, self.b, o.a, o.b
        beta_fp = type(a)(self.beta)
        return Fp2(a * c + b * d * beta_fp, a * d + b * c, self.beta)

    def conj(self):
        """共轭 a - bu"""
        return Fp2(self.a, -self.b, self.beta)

    def norm(self) -> Fp:
        """范数 N(z) = z * z_conj = a² - β·b² ∈ F_p"""
        beta_fp = type(self.a)(self.beta)
        return self.a * self.a - beta_fp * self.b * self.b

    def inv(self):
        """逆: z⁻¹ = z_conj / N(z)"""
        n_inv = self.norm().inv()
        return Fp2(self.a * n_inv, -self.b * n_inv, self.beta)

    def __eq__(self, o): return self.a == o.a and self.b == o.b
    def __repr__(self):  return f"({self.a.value} + {self.b.value}*u)"


# ============ 演示 ============
if __name__ == "__main__":
    # 1. F_7 基本运算
    F7 = make_fp(7)
    a = F7(3); b = F7(5)
    print(f"F_7: 3+5={a+b}, 3*5={a*b}, 3⁻¹={a.inv()}, 3^100={a**100}")

    # 2. Fermat 小定理: a^(p-1) = 1
    for x in range(1, 7):
        assert F7(x) ** 6 == F7(1)
    print("Fermat 小定理 in F_7 验证通过")

    # 3. F_{p²} 扩域 (p=7, β=-1=6, u²=-1)
    # 注: 7 ≡ 3 (mod 4), -1 是 F_7 的 NQR (因 (-1)^((7-1)/2) = (-1)^3 = -1)
    z = Fp2(F7(2), F7(3), beta=-1)  # 2 + 3u
    w = Fp2(F7(1), F7(4), beta=-1)  # 1 + 4u
    print(f"z = {z}, w = {w}")
    print(f"z + w = {z + w}")
    print(f"z * w = {z * w}")
    print(f"z⁻¹ = {z.inv()}")
    print(f"z * z⁻¹ = {z * z.inv()}")

    # 4. BLS12-381 base field prime (实际)
    BLS12_381_P = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab
    Fbls = make_fp(BLS12_381_P)
    print(f"\nBLS12-381 p 位长: {BLS12_381_P.bit_length()} bits")
    one = Fbls(1)
    print(f"1 + 1 = {one + one}")

    # 5. AES S-box 域: F_{2^8} = F_2[x]/(x⁸+x⁴+x³+x+1)
    # 这里只演示 F_2 上的 ord
    # 完整实现见 next-week extension

关键运行输出：

F_7: 3+5=Fp_7(1), 3*5=Fp_7(1), 3⁻¹=Fp_7(5), 3^100=Fp_7(2)
Fermat 小定理 in F_7 验证通过
z = (2 + 3*u), w = (1 + 4*u)
z + w = (3 + 0*u)
z * w = (4 + 4*u)
z⁻¹ = (5 + 6*u)
z * z⁻¹ = (1 + 0*u)
BLS12-381 p 位长: 381 bits

---

六、密码学应用关联

6.1 $\mathbb{F}_p$ — 一切公钥的基底

6.2 $\mathbb{F}_{p^k}$ — Pairing 与 ZK

• BLS12-381: 嵌入度 $k=12$，pairing 输出在 $\mathbb{F}_{p^{12}}^*$
• Groth16, KZG: 多项式系数在 $\mathbb{F}p$，但配对计算落在 $\mathbb{F}{p^{12}}$
• STARK / FRI: 基底 $\mathbb{F}p$ 但常用扩域 $\mathbb{F}{p^2}$ 做安全增强

6.3 $\mathbb{F}_{2^n}$ — 对称密码

• AES: S-box 是 $\mathbb{F}_{2^8}$ 上的求逆 + 仿射
• GCM: 认证用 $\mathbb{F}_{2^{128}}$ 上多项式
• Reed-Solomon / 编码: $\mathbb{F}{2^8}$ 或 $\mathbb{F}{2^{16}}$

---

七、真实参数

secp256k1 base field

$p = 2^{256} - 2^{32} - 977$ （注：此 $p$ 是 generalized Mersenne，便于约简）

Curve25519 base field

$p = 2^{255} - 19$

BLS12-381 base field

$p = 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272559787$ $\approx 2^{381}$

Goldilocks (Plonky2)

$p = 2^{64} - 2^{32} + 1$ （特殊形式让 mod 极快）

AES 域

$\mathbb{F}_{2^8}$，不可约多项式 $m(x) = x^8 + x^4 + x^3 + x + 1$

---

八、常见陷阱

1. 混淆环和域：$\mathbb{Z}/n\mathbb{Z}$ 当 $n$ 复合时不是域（有零因子）。RSA 用的是环不是域。
2. 不可约多项式选错：$\mathbb{F}_2[x]/\langle x^2 \rangle$ 不是域，$x$ 是零因子。必须不可约。
3. $\mathbb{F}_{p^2}$ 不等于 $\mathbb{Z}/p^2\mathbb{Z}$！前者是 $p^2$ 元的域，后者甚至不是域。$\mathbb{F}_{p^2}$ 必须用多项式商构造。
4. Frobenius 在素域上是恒等：因 $\mathbb{F}_p$ 上 $a^p = a$（FLT），所以 Frobenius 才在扩域上发挥作用。
5. NQR 选择：构造 $\mathbb{F}_{p^2}$ 时 $\beta$ 必须是非二次剩余，否则 $u^2 - \beta$ 可分解。
6. 域的"特征"和"阶"：$\mathbb{F}_{p^n}$ 阶 = $p^n$，特征 = $p$，乘法群阶 = $p^n - 1$。三者别混。

---

九、关键速查

class Fp:
    def __add__, __sub__, __mul__, inv, pow
class Fp2:
    def __add__, __sub__, __mul__, conj, norm, inv

---

十、面试题

Q1: 为什么不存在 6 元有限域？

答：根据 Galois 定理，有限域阶必为素数幂 $p^n$。$6 = 2 \cdot 3$ 不是素数幂，所以不存在 6 元域。 追问：但存在 6 元的环吗？是的，$\mathbb{Z}/6\mathbb{Z}$ 是 6 元环但不是域（$2 \cdot 3 = 0$ 但 $2, 3 \ne 0$，零因子存在）。

Q2: 解释 $\mathbb{F}_{2^8}$ 在 AES 中的具体作用。

答：AES 字节用 $\mathbb{F}_{2^8}$ 元素表示（8 bit ↔ 8 系数 mod 2 多项式）。S-box 计算是：

1. 求 $x^{-1}$（在 $\mathbb{F}_{2^8}$ 中，0 映到 0）
2. 仿射变换 $y = Ax^{-1} + b$（$A$ 是固定 $8 \times 8$ 矩阵）

非线性来自求逆，线性来自仿射。$\mathbb{F}_{2^8}$ 的乘法用 $x^8+x^4+x^3+x+1$ 模约。

Q3: $\mathbb{F}_p$ 与 $\mathbb{Z}/p^2\mathbb{Z}$ 有什么区别？

答：

• $\mathbb{F}_p$ 是 $p$ 元域
• $\mathbb{Z}/p^2\mathbb{Z}$ 是 $p^2$ 元环但不是域（$p \cdot p = 0$ 但 $p \ne 0$）
• $\mathbb{F}_{p^2}$ 是 $p^2$ 元域，构造为 $\mathbb{F}_p[x]/\langle f\rangle$，$f$ 二次不可约

虽然 $\mathbb{F}_{p^2}$ 和 $\mathbb{Z}/p^2\mathbb{Z}$ 都有 $p^2$ 个元素，但乘法结构完全不同。

Q4: 为什么 BLS12-381 用塔域 $\mathbb{F}{p^{12}}$ 而不直接 $\mathbb{F}{p^{12}}$ 计算？

答：直接在 $\mathbb{F}{p^{12}}$ 用 12 次不可约多项式做模约，乘法 $O(12^2)=144$ 次基础乘。塔分解 $\mathbb{F}p \to \mathbb{F}{p^2} \to \mathbb{F}{p^6} \to \mathbb{F}_{p^{12}}$ 利用 Karatsuba：$2 \times 2$ 乘 3 次基础乘（不是 4），$3 \times 3$ 乘 6 次（不是 9），最终 $\sim 54$ 次。配合特殊不可约多项式（如 $u^2+1, v^3-(u+1), w^2-v$）让模约近乎免费。

Q5: Frobenius 自同构在 ECDSA 验证中如何用到？

答：Frobenius $\phi: P \mapsto (x^p, y^p)$ 是椭圆曲线 endomorphism，满足特征方程 $\phi^2 - t\phi + p = 0$，其中 $t$ 是迹（Frobenius 迹）。Schoof's algorithm 通过模小素数 $\ell$ 计算 $t \mod \ell$ 来确定曲线点数 $#E = p + 1 - t$。这是 ECDSA 选曲线必做的步骤——必须知道点数才能选合适的子群阶。

---

十一、明日预告

Day 183: 椭圆曲线基础 — 把今天的有限域 $\mathbb{F}_p$ 当作"系数空间"，在上面定义曲线 $y^2 = x^3 + ax + b$。明天推导点加法的几何法则、代数公式、标量乘法，并用 Python 实现完整 EC 点加法算法。

核心问题：为什么椭圆曲线点构成一个群？无穷远点是什么？

参考文献：

• Lidl & Niederreiter, Finite Fields, Cambridge.
• Mullen & Panario, Handbook of Finite Fields, CRC.
• Galbraith, Mathematics of Public Key Cryptography, Ch. 2.
• BLS12-381 spec: https://hackmd.io/@benjaminion/bls12-381