有限域算术：从 AES 到 Reed-Solomon（1/4）

群环域公理、GF(p) 的模算术、费马小定理与逆元
系列导航：1. 数学基础与 GF(p) 素数域 · 2. 扩展域 GF(2^n) 与 AES · 3. Reed-Solomon 编解码与 C 实现 · 4. GHASH、Shamir 秘密共享与工程实战

摘录自：有限域算术：从 AES 到 Reed-Solomon

你每天都在跟有限域打交道，只是你可能不知道。

打开一个 HTTPS 网页，AES-GCM 加密流量时在 \(GF(2^8)\) 和 \(GF(2^{128})\) 上做乘法。手机扫一个二维码，Reed-Solomon 纠错码在 \(GF(2^8)\) 上做多项式求值。NAS 上跑 ZFS，它的校验和基于 Reed-Solomon 编码。你用的每一张 CD、每一张 DVD、每一块 SSD 的 ECC，底层都是有限域运算。

有限域（Finite Field），又叫伽罗瓦域（Galois Field），是一个只含有限个元素的集合，且在这个集合上定义了加减乘除四种运算，运算结果永远不会”溢出”到集合外面。这个性质使得它成为密码学和纠错编码的理想数学工具：你可以在有限的比特宽度内做完整的代数运算，不丢信息，不需要浮点数，不需要大整数库。

本文从群、环、域的公理出发，逐步构造 GF(p) 和 \(GF(2^n)\)，然后深入 AES、Reed-Solomon、GHASH、Shamir 秘密共享等具体应用，最后给出一个完整的 C 实现和工程实战经验。

GF(2^8) 乘法流程

代数结构速览：群、环、域

在讨论有限域之前，需要回顾三个代数结构。这不是纯数学的自娱自乐——理解这些公理，你才能明白为什么 AES 选择了特定的不可约多项式，为什么 Reed-Solomon 编码天然具有纠错能力。

群（Group）

一个集合 G 配上一个二元运算 _，_满足以下四条公理就构成一个群 \((G, *)\)：

封闭性：对任意 a, b 属于 G，\(a * b\) 也属于 G。
结合律：\((a * b) * c = a * (b * c)\)。
单位元：存在元素 e 属于 G，使得对任意 a 属于 G，e * a = a * e = a。
逆元：对任意 a 属于 G，存在 \(a^{-1}\) 属于 G，使得 \(a * a^{-1} = a^{-1} * a = e\)。

如果还满足交换律 \(a * b = b * a\)，就叫阿贝尔群（交换群）。

最常见的例子：整数集合在加法下构成阿贝尔群，单位元是 0，a 的逆元是 -a。

环（Ring）

一个集合 R 配上加法 + 和乘法 *，满足：

\((R, +)\) 是阿贝尔群（加法单位元记为 0）。
乘法满足结合律。
乘法对加法满足分配律：\(a * (b + c) = a * b + a * c\)。

如果乘法还有单位元 1，就叫含幺环。如果乘法还满足交换律，就叫交换环。

整数集合 Z 就是一个交换环。但 Z 不是域——因为 2 没有乘法逆元（1/2 不是整数）。

域（Field）

一个集合 F 配上加法 + 和乘法 *，满足：

\((F, +)\) 是阿贝尔群。
\((F \setminus \{0\}, *)\) 是阿贝尔群（非零元素在乘法下构成阿贝尔群）。
乘法对加法满足分配律。

域的核心要求是：每个非零元素都有乘法逆元。这意味着除法（除零以外）总是可行的。

有理数 \(Q\)、实数 \(R\)、复数 \(C\) 都是域，但它们是无限域。我们关心的是有限域：元素个数有限的域。

有限域的基本定理

有限域的存在性和唯一性由以下定理完全刻画：

定理：有限域的元素个数必为素数的幂 \(p^n\)，其中 \(p\) 是素数，\(n\) 是正整数。反之，对任意素数幂 \(p^n\)，恰好存在一个（同构意义下）含 \(p^n\) 个元素的有限域，记作 \(GF(p^n)\)。

首先我们有：令 \((𝐹, +, ·)\) 是一个域，而 \(char(𝐹) ≠ 0\)，则 \(char(𝐹) = 𝑝\) 是一个素数。

那么可以证明有限域的阶一定是某个素数的幂次：

=> 任何有限域的乘法群（\(\mathbb{F}_{p^n}^\times\)）都是阶为\(p^n - 1\)的循环群(去掉一个 0)。

这个定理告诉我们两件事：

不存在含 6 个元素的有限域（\(6 = 2 * 3\)，不是素数幂）。
\(GF(256)\) 是唯一的——不同构造方法（选不同的不可约多项式）得到的 \(GF(256)\) 在结构上是同构的。

本原多项式和最小多项式

令 \((R, +, \cdot)\) 是一个唯一分解整环，而 \(f = \sum_n a_n x^n \in R[x] \setminus \{0\}\)，则我们定义 \(f\) 的多项式容量，记作 \(\text{cont}(f)\)，定义为 \(f\) 上所有系数的最大公因数，即

\[\text{cont}(f) = \gcd(a_0, \cdots, a_n)\]

其中 \(a_n\) 是 \(f\) 的首项系数。而 \(\text{cont}(f)\) 是不一定唯一的，但是最多相差一个单位。

假如 \(\text{cont}(f) = 1\)，我们就称 \(f\) 是个本原多项式。

令 \(F/E\) 是一个域扩张，而\(a \in F\)。若 \(E(a)/E\) 是个有限扩张，则存在唯一的首一非零多项式 \(p(x)\)，使得

\[\forall f(x) \in E[x], (f(a) = 0 \implies p(x) \mid f(x))\]

我们称这个多项式为 \(a\) 在域 \(E\) 上的最小多项式。

唯一的首一多项式 \(p(x)\)正是满足 \(p(a)=0\)的次数最低的首一多项式

例如 \(f(x)=(x−1)(x+1)\)，那么 \(a = 1\) 的最小多项式是 \(x−1\)，因为它是首一的、以 \(1\)为根的最低次多项式，并且整除任何以 \(1\)为根的多项式（如 \((x−1)(x+1)\)）。

有限域与分裂域

我们有引理：

令 \(F/E\) 是一个域扩张，而 \(a \in F\)。假设 \(E(a)/E\) 是个有限扩张，令 \(p(x)\) 是 \(a\) 在 \(E\) 上的最小多项式，则

\[E[x]/(p(x)) \simeq E(a)\]

令 \((F, +, \cdot)\) 是个阶为 \(q = p^n\) 的有限域。则：

\(F\) (记为\(\mathbb{F}_q\)或 \(GF(q)\))是 \(x^{p^n} - x\)在\(\mathbb{F}_p\)上的一个分裂域。

令 \((F_1, +, \cdot)\) 和 \((F_2, +, \cdot)\) 是阶相等的有限域，则\(F_1 \simeq F_2\)。假设 \(|F_1| = |F_2| = q = p^n\)，则我们在同构的意义下，记\(\mathbb{F}_q = \mathbb{F}_{p^n}\)为这样的有限域。—— 分裂域的唯一性

根据2，任何阶为\(q=p^n\)的有限域\(F\) 都是多项式 \(x^{p^n} - x\)在基域 \(\mathbb{F}_p\)上的分裂域。这意味着：

\(f(x)\)在 \(\mathbb{F}_p\)上可以分解为一次因式的乘积，即所有根均属于 \(F\)(分裂域定义）；
\(F\)包含且仅包含 \(f(x)\)的全部 \(p^n\)个根（包括0和1）。

根据 3 分裂域的唯一性：

对于固定的 \(p\)和 \(n\)，多项式 \(x^{p^n} - x\)在 \(\mathbb{F}_p\)上的分裂域无论怎样构造，都与 \(\mathbb{F}_{p^n}\)同构。
因此，所有阶为\(p^n\)的有限域本质上都是\(\mathbb{F}_{p^n}\)，只是构造方式不同而已。

这两个引理告诉我们：对于固定的\(p\)和\(n\)，\(\mathbb{F}_{p^n}\)是唯一存在的，并且它就是\(x^{p^n} - x\)的分裂域。

设 \(f(x) \in \mathbb{F}_p[x]\) 是一个 \(n\) 次不可约多项式。考虑商环

\[R = \mathbb{F}_p[x] \big/ (f(x)),\]

其中 \((f(x))\) 是 \(f(x)\) 生成的主理想，元素 \(g(x)\) 所在的陪集为

\[g(x) + (f(x)) = \{\, g(x) + h(x)\cdot f(x) \mid h(x) \in \mathbb{F}_p[x] \,\}.\]

因为 \(f\) 不可约，理想 \((f)\) 是极大理想，所以 \(R\) 是一个域。

设 \(n = \deg f(x)\)（假设 \(f\) 首一，否则可标准化）。

由域上的多项式环是欧几里得整环 =>

每个陪集中恰好有一个次数严格小于 \(n\) 的多项式（包括零多项式）。这个多项式(标准代表元：次数小于 \(n\))由带余除法唯一确定：

\[g(x) = q(x)f(x) + r(x), \quad \deg r < n\]

于是我们可以把商环的元素等同于这些“低次多项式”：

\[\mathbb{F}_p[x]/(f(x)) \cong \{ a_0 + a_1 x + \cdots + a_{n-1} x^{n-1} \mid a_i \in \mathbb{F}_p \}\]

这正好是一个 \(n\) 维的 \(\mathbb{F}_p\)-向量空间（基为 \(1, x, \ldots, x^{n-1}\)），共有 \(p^n\) 个元素。

即： \(\dim_{\mathbb{F}_p} R = n\) (\(R\)作为 \(\mathbb{F}_p\)-向量空间的维数等于 \(\text{deg}f=n\))， \(R\)是\(\mathbb{F}_p\)的\(n\)次扩域。\(R\) 中的每个元素都可以唯一表示为次数小于 \(n\)的多项式，即形如 \(a_0+a_1x+⋯+a_{n−1}x^{n−1}\)，其中 \(a_i∈\mathbb{F}_p\)。这样的表示共有 \(p^n\)种，因此 \(R\)恰有 \(p^n\)个元素。

根据引理 3，这样的扩域唯一（同构意义下），所以\(R \cong \mathbb{F}_{p^n}.\) 即：

\(\boxed{\mathbb{F}_p[x] / (f(x)) \cong \mathbb{F}_{p^n}}\) 其中 \(f(x) \in \mathbb{F}_p[x]\) 是一个 \(n\) 次不可约多项式.

另一方面，在商环\(R = \mathbb{F}_p[x] / (f(x))\) 中，记元素\(\alpha = x + (f(x))\)，即 \(x (\in \mathbb{F}_p[x])\)所在的陪集，记为\(\bar{x}\)。

由于商映射\(\pi : \mathbb{F}_p[x] \to R\) 是环同态，根据商环定义：

\(\pi(x) = x + (f(x)) = \alpha\),
\(\pi(f(x)) = f(x) + (f(x)) = 0_R\).

而环同态保持多项式运算，因此：

\[f(\alpha) = f(\pi(x)) = \pi(f(x)) = f(x) + (f(x)) = \bar{0}.\]

（\(f(x) \sim 0\)）

集合 \(x+(f(x))\)就是根 \(α\)在商环中的表现形式：

从构造角度看，它是陪集（集合）。
从代数角度看，它是域中的元素（根）。

由引理 1（商环同构于单扩张）

\(R\) 本身是一个域（因为 \(f\)不可约,\((f(x))\)是一个极大理想）。
\(α\)是 \(R\)中的一个元素，且 \(f(α)=0\)。
在 \(R\)内部，我们可以考虑 \(\mathbb{F}_p(α)\)：即 \(R\)中包含 \(\mathbb{F}_p\)和 \(α\)的最小子域。

得到

\[\mathbb{F}_p[x]/(f(x)) \cong \mathbb{F}_p(\alpha).\]

其实：

\(R\)包含 \(\mathbb{F}_p\)和 \(α\)，所以 \(\mathbb{F}_p(α)⊆R\)。
另一方面，\(R\)中每个元素都可以唯一表示为 \(a_0+a_1α+⋯+a_{n−1}α^{n−1}\)（\(n=\text{deg}f\)），因此 \(R⊆\mathbb{F}_p(α)\)。
故 \(\mathbb{F}_p(α)=R\)，两者是同一个域，同构映射就是恒等映射。

即

\[\boxed{\mathbb{F}_{p^n} \cong \mathbb{F}_p[x] / (f(x)) \cong \mathbb{F}_p(\alpha)}.\]

根据有限域的基本定理\(\mathbb{F}_{p^n}\)乘法阶为 \(p^n−1\)。

因此，不可约多项式\(f(x)\)决定了\(\mathbb{F}_p\)的一个\(n\)次扩域\(\mathbb{F}_{p^n}\)，并且\(\alpha\)是该扩域的一个本原元（即生成元）当且仅当\(\alpha\)的乘法阶为\(p^n - 1\)。

具体例子：

\(\mathbb{F}_2\) 和 \(f(x)=x^2+x+1\)

基础域 \(\mathbb{F}_2 = \{0,1\}\)

加法：\(0+0=0\), \(0+1=1\), \(1+0=1\), \(1+1=0\)
乘法：\(0\cdot0=0\), \(0\cdot1=0\), \(1\cdot0=0\), \(1\cdot1=1\)

不可约多项式 \(f(x)=x^2+x+1\)

在 \(\mathbb{F}_2\) 上不可约（因为 \(f(0)=1\), \(f(1)=1\)，没有根）。

商环 \(R = \mathbb{F}_2[x]/(f(x))\)

元素是陪集，每个陪集用次数小于2的多项式作为代表元。
所有代表元：\(0\), \(1\), \(x\), \(x+1\)。
因此 \(R\) 有4个元素：\(\bar{0} = 0 + (f)\), \(\bar{1} = 1 + (f)\), \(\alpha = x + (f)\), \(\alpha+1 = (x+1) + (f)\)（因为 \(\bar{1}+\alpha = \alpha+1\)）。

元素 \(\alpha = x + (f)\)

它是一个陪集（集合），但在 \(R\) 中被视为一个元素。
关键关系：因为 \(f(x) = x^2+x+1 \in (f)\)，所以在商环中 \(f(\alpha)=0_R\)，即：\(\alpha^2 + \alpha + 1 = 0 \quad \Longrightarrow \quad \alpha^2 = \alpha + 1\)（因为 \(-1=1\) in \(\mathbb{F}_2\)）。

乘法表（验证域结构）

利用 \(\alpha^2 = \alpha+1\) 计算所有乘积：

\(\alpha \cdot \alpha = \alpha^2 = \alpha+1\)
\(\alpha \cdot (\alpha+1) = \alpha^2 + \alpha = (\alpha+1) + \alpha = 1\)
\((\alpha+1) \cdot (\alpha+1) = \alpha^2 + 2\alpha + 1 = (\alpha+1) + 0 + 1 = \alpha\)
\(\alpha \cdot 1 = \alpha\)，等等。

因此 \(R\) 是一个域（4元域，记作 \(\mathbb{F}_4\)）。

\(\mathbb{F}_2(\alpha)\) 是什么？

\(\mathbb{F}_2(\alpha)\) 是包含 \(\mathbb{F}_2\) 和 \(\alpha\) 的最小子域。
由于 \(R\) 已经包含 \(\mathbb{F}_2\) 和 \(\alpha\)，且 \(R\) 是域，所以 \(\mathbb{F}_2(\alpha) \subseteq R\)。
但 \(R\) 中每个元素都可以写成 \(a + b\alpha\)（\(a,b\in\mathbb{F}_2\)），所以 \(R \subseteq \mathbb{F}_2(\alpha)\)。
因此 \(\mathbb{F}_2(\alpha) = R\)，即 \(\mathbb{F}_2(\alpha) = \{0,1,\alpha,\alpha+1\}\)。

概念	例子	本质
多项式 \(f(x)\)	\(x^2+x+1\)	用来生成理想的“模”
陪集 \(\alpha\)	\(x + (f)\)	商环中的一个元素，即“新数”
扩域 \(\mathbb{F}_2(\alpha)\)	\(\{0,1,\alpha,\alpha+1\}\)	由 \(\mathbb{F}_2\) 添加 \(\alpha\) 得到的域

所以，\(\mathbb{F}_p(\alpha)\)是“原本的有限域加上一个新元素（陪集）”，这个新元素满足\(f(\alpha)=0\)，从而使得扩域成为\(p^n\)元域。

多项式的阶

定义多项式 \(f(x)\) 的阶为最小的正整数 \(e\) 使得\(f(x) \mid (x^e - 1)\)在\(\mathbb{F}_p[x]\)中.

若 \(f(x) \mid (x^e - 1)\)，则在商环 \(R = \mathbb{F}_p[x] / (f(x))\) 中有 \(\alpha^e - 1 = 0\)，即 \(\alpha^e = 1\)，所以 \(\operatorname{ord}(\alpha) \mid e\)。

\(x^e - 1 = g(x)*f(x) (g(x) \in \mathbb{F}_p[x])\)，带入环同态\(\pi : \mathbb{F}_p[x] \to R\),\(\alpha^e - 1 = f(\alpha)g(\alpha) = 0\)

反之，若\(\operatorname{ord}(\alpha) \mid e\), 即\(\alpha^e = 1\)，则 \(\alpha\) 是 \(x^e - 1\) 的根。由于 \(f(x)\) 是 \(\alpha\) 的最小多项式（因为 \(f\) 不可约且 \(f(\alpha)=0\)），所以 \(f(x) \mid (x^e - 1)\)。

因此，最小的\(e\)使得\(f(x) \mid (x^e - 1)\)正好就是\(\alpha\)的乘法阶，即多项式的阶\(e_f = \operatorname{ord}(\alpha).\)

我们知道 \(\mathbb{F}_{p^n}^\times\) 是阶为 \(p^n - 1\) 的循环群。所以 \(\alpha\) 的乘法阶 \(\operatorname{ord}(\alpha)\) 整除 \(p^n - 1\)。

当 \(\operatorname{ord}(\alpha) = p^n - 1\) 时，\(\alpha\) 生成整个乘法群，称为本原元。此时 \(f(x)\) 称为本原多项式。
等价地，多项式的阶 \(e_f = p^n - 1\)。

于是我们得到两种等价的定义：

定义 A（阶）：\(n\) 次不可约多项式 \(f(x) \in \mathbb{F}_p[x]\) 称为本原的，如果它的阶等于 \(p^n - 1\)。

定义 B（生成元）：在商环 \(\mathbb{F}_p[x]/(f(x)) \cong \mathbb{F}_{p^n}\) 中，元素 \(x\)（即 \(\alpha = x + (f(x))\)）的乘法阶恰为 \(p^n - 1\)。

应用到 AES 多项式

AES 使用的多项式是\(P(x) = x^8 + x^4 + x^3 + x + 1 \in \mathbb{F}_2[x].\)

已知它是 \(\mathbb{F}_2\) 上的 8 次不可约多项式（30 个中最小的一个），并且是本原多项式。

根据定义 B，在 \(\mathbb{F}_2[x]/(P(x)) \cong \mathbb{F}_{2^8}\) 中，元素 \(x\) 的乘法阶为 \(2^8 - 1 = 255\)。因此
\(\{ x^0, x^1, x^2, \dots, x^{254} \}\)恰好遍历所有 255 个非零元素。

这正是 AES 中字节运算的基础：每个非零字节（看作 \(\mathbb{F}_{2^8}\) 中的元素）都可以表示为 \(x\) 的幂次，从而方便进行乘法、求逆等运算。

GF(p)：素数域的算术

当 n = 1 时，\(GF(p)\) 就是模 \(p\) 的整数集合 \(\{0, 1, 2, …, p-1\}\)，加法和乘法都在模 \(p\) 下进行。

为什么 p 必须是素数

模 \(n\) 算术中，一个元素 \(a\) 有乘法逆元的充要条件是 \(gcd(a, n) = 1\)。如果 n 是素数，那么 \(\{1, 2, …, n-1\}\) 中的每个元素都与 n 互素，因此都有逆元。如果 \(n\) 不是素数，比如 \(n = 6\)，那么 \(2 \times 3 \equiv 0 \pmod{6}\)，两个非零元素相乘得到零——这就是所谓的零因子，有零因子的结构不可能是域。

元素 \(a\in R\)称为零因子（zero divisor），如果：

\(a \neq 0\)，并且
存在某个 \(b \neq 0\)（也属于 R）使得\(a⋅b=0\).

根据定义 => 零因子一定不可逆⇒ 只要环里有零因子，它就当不了域。

GF(p) 的四则运算

以 \(GF(7)\) 为例：

plain

加法：3 + 5 = 8 mod 7 = 1
减法：2 - 5 = -3 mod 7 = 4
乘法：3 * 4 = 12 mod 7 = 5
除法：3 / 4 = 3 * 4^(-1) mod 7 = 3 * 2 mod 7 = 6
      (因为 4 * 2 = 8 mod 7 = 1，所以 4^(-1) = 2)

求逆元：扩展欧几里得算法

求 a 在 \(GF(p)\) 中的逆元，等价于求 a * x + p * y = 1 的整数解 x。这正是扩展欧几里得算法的经典应用。

/* 扩展欧几里得算法，返回 gcd(a, b)，同时求出 x, y 使得 a*x + b*y = gcd(a,b) */
int ext_gcd(int a, int b, int *x, int *y)
{
    if (b == 0) {
        *x = 1;
        *y = 0;
        return a;
    }
    int x1, y1;
    int g = ext_gcd(b, a % b, &x1, &y1);
    *x = y1;
    *y = x1 - (a / b) * y1;
    return g;
}

/* 求 a 在模 p 下的逆元 */
int mod_inv(int a, int p)
{
    int x, y;
    ext_gcd(a, p, &x, &y);
    return ((x % p) + p) % p;
}

另一种方法是费马小定理：\(a^{p-1} \equiv 1\pmod{p} => a^{-1} = a^{p-2} \;mod \;p\)。这在\(p\)很大时可以用快速幂高效计算，但在\(p\)较小时不如扩展欧几里得直接。

GF(p) 的乘法群是循环群

\(GF(p)\) 的非零元素在乘法下构成一个 \(p-1\) 阶的循环群。也就是说，存在一个生成元（原根）\(g\)，使得 {\(g^0, g^1, g^2, …, g^{p-2}\)} 恰好遍历 {1, 2, …, p-1}。

以 GF(7) 为例，3 是一个原根：

plain

3^0 = 1
3^1 = 3
3^2 = 2
3^3 = 6
3^4 = 4
3^5 = 5
3^6 = 1 (回到起点)

这个性质在离散对数密码学（DH 密钥交换、ElGamal 加密）和 Shamir 秘密共享中至关重要。

有限域算术：从 AES 到 Reed-Solomon（1/4） ​

代数结构速览：群、环、域 ​

群（Group） ​

环（Ring） ​

域（Field） ​

有限域的基本定理 ​

本原多项式和最小多项式 ​

有限域与分裂域 ​

具体例子： ​

多项式的阶 ​

GF(p)：素数域的算术 ​

为什么 p 必须是素数 ​

GF(p) 的四则运算 ​

求逆元：扩展欧几里得算法 ​

GF(p) 的乘法群是循环群 ​