§10.3 有限域的应用

本节学习目标

1. 理解有限域在编码理论中的核心角色：线性码、循环码与理想的一一对应。
2. 通过具体的 Reed–Solomon 码编码/译码过程，看到 ${\mathbb{F}}_q$ 上多项式插值的直接应用。
3. 理解有限域在密码学中的地位：离散对数、Diffie–Hellman、AES 中 ${\mathbb{F}}_{2^8}$ 的作用。
4. 通过椭圆曲线 ${\mathbb{F}}_p$ 点计数的例子，体会 Weil 猜想如何将有限域上的代数几何与数论连接。
5. 掌握分圆多项式在有限域上的分解规律，并能对具体的 $(q,n)$ 做出完整的不可约因子分解。

直觉 从纯数学到应用

有限域虽然是纯粹的代数对象，但它们在现代信息科学中扮演核心角色。密码学、编码理论、组合设计、甚至量子计算都深度依赖有限域的结构。Galois 理论保证了这些应用的数学基础。

本节展示四个方向的应用。每个方向都从具体计算出发，让读者看到 ${\mathbb{F}}_q$ 的结构定理（§10.1 的构造、§10.2 的 Frobenius）如何直接转化为实际工具。

---

10.3.1 纠错码

直觉 为什么纠错码需要有限域？

信息在物理信道中传输时会发生噪声干扰（如 CD 上的划痕、无线电波的干扰）。纠错码的思路是：发送 $n$ 个符号的码字（codeword），即使其中 $t$ 个被损坏，接收方仍能恢复原始信息。

关键在于：编码和译码算法需要对符号做加、减、乘、除运算。实数域太大且精度问题使得计算不可靠。有限域 ${\mathbb{F}}_q$ 提供了精确的算术，不会有舍入误差，且代数结构（有限性、Frobenius 自同构等）使得高效算法成为可能。

定义 10.3.1 ${\mathbb{F}}_q^n$ 的一个**线性码（linear code）**是一个 ${\mathbb{F}}_q$ -子空间 $C\subseteq {\mathbb{F}}_q^n$ 。 $C$ 的参数为 $[n,k,d{]}_q$ ：

• 长度（length） $n$ ：码字的符号数。
• 维数（dimension） $k={\dim }_{{\mathbb{F}}_q}C$ ：信息位数（ $|C|=q^k$ ）。
• 最小距离（minimum distance） $d=\underset{c\ne c^{\prime }\in C}{min}|\{i:c_i\ne c_i^{\prime }\}|$ ：可纠正的最多错误数为 $\lfloor (d-1)/2\rfloor$ 。

定义 10.3.2 一个线性码 $C$ 是循环码（cyclic code），如果码字的每次循环移位仍是码字： $(c_0,c_1,\dots ,c_{n-1})\in C\Rightarrow (c_{n-1},c_0,\dots ,c_{n-2})\in C$ 。

定理 循环码与理想

循环码与 ${\mathbb{F}}_q[x]/(x^n-1)$ 的理想一一对应。每个循环码 $C$ 由一个唯一的首一多项式 $g(x)\mid (x^n-1)$ 生成（ $g$ 称为生成多项式），且 $\dim C=n-\mathrm{deg}g$ 。

证明. 将码字 $(c_0,\dots ,c_{n-1})$ 与多项式 $c(x)=c_0+c_{1}x+\cdots +c_{n-1}{x}^{n-1}$ 对应。循环移位对应于乘以 $x$ （模 $x^n-1$ ）。循环码恰好是 ${\mathbb{F}}_q[x]/(x^n-1)$ 中对乘以 $x$ 封闭的子空间，即理想。由于 ${\mathbb{F}}_q[x]$ 是主理想环， ${\mathbb{F}}_q[x]/(x^n-1)$ 的理想由 $x^n-1$ 的因子生成。维数公式： $\dim C=\mathrm{deg}(x^n-1)-\mathrm{deg}g=n-\mathrm{deg}g$ 。 $◻$

例 具体的循环码

在 ${\mathbb{F}}_2[x]/(x^7-1)$ 中， $x^7-1=(x+1)(x^3+x+1)(x^3+x^2+1)$ 。

取 $g(x)=x^3+x+1$ （不可约，见 §4.2 的 $p=2,n=3$ 例子）。生成的循环码：

$$C=\{f(x)\cdot g(x)mod(x^7-1):\mathrm{deg}f<4\}$$

$\dim C=7-3=4$ ，所以 $C$ 有 $2^4=16$ 个码字。这是 $[7,4,3{]}_2$ 码——著名的 Hamming 码，可以纠正 1 位错误。

编码：消息 $m(x)=m_0+m_{1}x+m_2{x}^2+m_3{x}^3$ ，码字 $c(x)=m(x)\cdot g(x)$ 。

译码：收到 $r(x)$ ，计算 $s(x)=r(x)modg(x)$ （伴随式，syndrome）。 $s=0$ 表示无错误； $s\ne 0$ 定位错误位置。

Galois 理论联系： $g(x)$ 的不可约性确保了码的最优距离。不可约因子的选择直接决定了码的参数——这正是 §10.1 中 ${\mathbb{F}}_q$ 上多项式分解理论的直接应用。

Reed–Solomon 码

定理 Reed–Solomon 码

设 $\alpha$ 是 ${\mathbb{F}}_q$ 的本原元（ $q=p^m$ ）。Reed–Solomon 码$\mathrm{RS}(k,n)$ （ $n=q-1$ ）定义为：

$$C=\{(f(1),f(\alpha ),f({\alpha }^2),\dots ,f({\alpha }^{n-1})):f\in {\mathbb{F}}_q[x],\mathrm{deg}f<k\}$$

$C$ 是 $[n,k,n-k+1{]}_q$ 码，达到了 Singleton 界（ $d\le n-k+1$ ），是最大距离可分码（MDS 码）。

例 Reed–Solomon 码 $\mathrm{RS}(3,7)$ 在 ${\mathbb{F}}_8$ 上

取 $q=8=2^3$ 。由 §10.1， ${\mathbb{F}}_8={\mathbb{F}}_2[t]/(t^3+t+1)$ ，本原元 $\alpha =t$ （ $t^3=t+1$ ）。

$\alpha$ 的幂次表：

$i$	${\alpha }^i$	二进制 $(c_2,c_1,c_0)$
0	$1$	$(0,0,1)$
1	$\alpha$	$(0,1,0)$
2	${\alpha }^2$	$(1,0,0)$
3	${\alpha }^3=\alpha +1$	$(0,1,1)$
4	${\alpha }^4={\alpha }^2+\alpha$	$(1,1,0)$
5	${\alpha }^5={\alpha }^2+\alpha +1$	$(1,1,1)$
6	${\alpha }^6={\alpha }^2+1$	$(1,0,1)$

$n=q-1=7$ 。 $\mathrm{RS}(3,7)$ ：消息为 $(m_0,m_1,m_2)\in {\mathbb{F}}_8^3$ ，对应多项式 $f(x)=m_0+m_{1}x+m_2{x}^2$ 。

编码：发送 $(f(1),f(\alpha ),f({\alpha }^2),f({\alpha }^3),f({\alpha }^4),f({\alpha }^5),f({\alpha }^6))$ 。

例如 $f(x)=1+\alpha x+{\alpha }^2{x}^2$ ：

• $f(1)=1+\alpha +{\alpha }^2$
• $f(\alpha )=1+{\alpha }^2+{\alpha }^4=1+{\alpha }^2+{\alpha }^2+\alpha =1+\alpha ={\alpha }^3$
• $f({\alpha }^2)=1+{\alpha }^3+{\alpha }^6=1+\alpha +1+{\alpha }^2+1={\alpha }^2+\alpha +1={\alpha }^5$

（其余类推。）

参数： $[7,3,5{]}_8$ 码，最小距离 $d=7-3+1=5$ 。可纠正 $\lfloor 4/2\rfloor =2$ 个符号错误。

关键观察：每个 ${\mathbb{F}}_8$ 的元素都可以用其 $\alpha$ 的幂次表示（由 §10.2 的本原元理论），乘法简化为指数加法模 7。这是 Reed–Solomon 码高效实现的核心。

直觉 Reed–Solomon 码为什么达到最优距离？

RS 码的本质是多项式插值： $\mathrm{deg}<k$ 的多项式由 $k$ 个值唯一确定。因此 $n$ 个取值中任意 $k$ 个都足以恢复整个多项式，从而纠正 $n-k$ 个错误。这是 Lagrange 插值定理的编码理论版本——代数基础直接转化为工程能力。

RS 码的应用：

• CD/DVD：使用 ${\mathbb{F}}_{2^8}$ 上的 RS 码，即使碟片被划伤也能播放。
• QR 码：RS 码使得二维码即使部分被遮挡也能扫描。
• 深空通信：旅行者号探测器使用 RS 码将数据从太阳系边缘传回地球。
• RAID 6：分布式存储系统用 RS 码实现双磁盘容错。

---

10.3.2 密码学

离散对数与 Diffie–Hellman

定义 10.3.3 设 $G={\mathbb{F}}_q^{\times }$ （循环群，阶 $q-1$ ）， $g$ 为生成元。离散对数问题（DLP）：给定 $g,h\in G$ ，找到整数 $x\in \{0,1,\dots ,q-2\}$ 使得 $g^x=h$ 。

定理 Diffie–Hellman 密钥交换

Alice 选随机 $a\in \{1,\dots ,q-2\}$ ，发送 $A=g^a$ ；Bob 选随机 $b$ ，发送 $B=g^b$ 。共享密钥为 $K=g^{ab}=A^b=B^a$ 。

安全性基础：计算 Diffie–Hellman 假设（CDH）——给定 $g,A=g^a,B=g^b$ ，在不知道 $a$ 或 $b$ 的情况下计算 $g^{ab}$ 是计算上困难的。

例 离散对数的计算

在 ${\mathbb{F}}_{11}^{\times }$ （阶 10，生成元 $g=2$ ）中：

$x$	$0$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$
$2^{x}mod11$	$1$	$2$	$4$	$8$	$5$	$10$	$9$	$7$	$3$	$6$

${\log }_2(9)=6$ （因为 $2^6=64=5\cdot 11+9\equiv 9(\mathrm{mod}11)$ ）。

Diffie–Hellman 协议：Alice 选 $a=3$ ，发送 $A=2^3=8$ 。Bob 选 $b=5$ ，发送 $B=2^5=10$ 。共享密钥 $K=2^{15}=2^{15mod10}=2^5=10$ 。

验证： $A^b=8^{5}mod11$ 。 $8^2=64\equiv 9$ ， $8^4\equiv 81\equiv 4$ ， $8^5\equiv 32\equiv 10$ 。✓ $B^a={10}^{3}mod11=1000mod11=10$ 。✓

有限域大小与安全性

${\mathbb{F}}_{11}^{\times }$ 只有 10 个元素，离散对数可以穷举。实际密码学使用 ${\mathbb{F}}_q$ ， $q\approx 2^{256}$ ，离散对数的已知最快算法（数域筛法）时间复杂度仍为亚指数级别。 ${\mathbb{F}}_q$ 中 $\log$ 的计算困难性是整个 Diffie–Hellman、ElGamal、DSA 等密码方案的安全基础。

AES 与 ${\mathbb{F}}_{2^8}$

例 AES 加密中的有限域

AES（Advanced Encryption Standard） 是全球使用最广泛的对称加密标准。其核心操作全部发生在 ${\mathbb{F}}_{2^8}={\mathbb{F}}_2[t]/(t^8+t^4+t^3+t+1)$ 上。

AES 的关键步骤涉及 ${\mathbb{F}}_{2^8}$ 的三种运算：

1. SubBytes（字节替换）：将每个字节 $b\in {\mathbb{F}}_{2^8}$ 映射为 $b^{-1}$ （在 ${\mathbb{F}}_{2^8}^{\times }$ 中求逆），再加上一个仿射变换。求逆运算的非线性性是 AES 安全性的核心。

2. MixColumns（列混合）：将每 4 个字节视为 ${\mathbb{F}}_{2^8}^4$ 中的向量，乘以一个固定的 $4\times 4$ 矩阵。矩阵的元素来自 ${\mathbb{F}}_{2^8}$ ，矩阵可逆性保证了解密的可行性。

3. 密钥扩展：使用 ${\mathbb{F}}_{2^8}$ 中的 $\alpha =t$ （本原元）作为轮常数，确保每轮子密钥不同。

为什么选择 ${\mathbb{F}}_{2^8}$ ？ 因为计算机的字节（byte）恰好是 8 位， ${\mathbb{F}}_{2^8}$ 的每个元素可以自然对应一个字节。 ${\mathbb{F}}_{2^8}$ 上的加法就是异或（XOR），乘法可以用查表或移位实现。有限域的精确算术保证了加密和解密的完美对称性。

注 椭圆曲线与有限域

现代密码学（如 ECDSA、EdDSA）使用有限域上的椭圆曲线。椭圆曲线 $E({\mathbb{F}}_q)$ 的点构成一个近似循环的阿贝尔群，其上的离散对数问题比 ${\mathbb{F}}_q^{\times }$ 上更难（需要亚指数或指数时间算法），因此可以用更短的密钥实现相同的安全级别。

例如 Bitcoin 使用 secp256k1 曲线，定义在 ${\mathbb{F}}_p$ （ $p$ 为 256 位素数）上。256 位的椭圆曲线密钥提供的安全性约等于 3072 位的 RSA 密钥。有限域越"结构化"（如 ${\mathbb{F}}_{2^m}$ ），安全分析越复杂——某些攻击利用了 ${\mathbb{F}}_{2^m}$ 的特殊结构。

---

10.3.3 有限域上的代数几何

直觉 为什么要在有限域上研究代数几何？

经典代数几何研究代数闭域（如 $\mathbb{C}$ ）上的簇。但有限域上的代数几何有一个独特的优点：有理点是有限的，可以精确计数。

这个看似简单的事实蕴含着深刻的数学结构。一个 ${\mathbb{F}}_q$ 上的代数簇 $X$ 的 ${\mathbb{F}}_{q^r}$ -有理点个数 $N_r=|X({\mathbb{F}}_{q^r})|$ 编码了关于 $X$ 的大量拓扑和算术信息。Weil 猜想精确描述了这种编码关系。

定理 Weil 猜想（有限域情形）

设 $X$ 是 ${\mathbb{F}}_q$ 上的 $d$ 维光滑射影簇， $N_r=|X({\mathbb{F}}_{q^r})|$ 为 $X$ 在 ${\mathbb{F}}_{q^r}$ 上的有理点个数。定义 Zeta 函数：

$$Z(X,t)=\exp (\sum _{r=1}^{\mathrm{\infty }}\frac{N_r}{r}{t}^r)$$

则：

(i) 有理性：$Z(X,t)\in \mathbb{Q}(t)$ （是有理函数）。

(ii) 函数方程：$Z(X,1/q^{d}t)=\pm q^{d\chi /2}{t}^{\chi }\cdot Z(X,t)$ （ $\chi$ 为 Euler 示性数）。

(iii) Riemann 假设：$Z(X,t)=\frac{P_1(t)P_3(t)\cdots P_{2d-1}(t)}{P_0(t)P_2(t)\cdots P_{2d}(t)}$ ，其中 $P_i(t)=\prod _j(1-{\alpha }_{ij}t)$ ， $|{\alpha }_{ij}|=q^{i/2}$ 。

例 椭圆曲线 $y^2=x^3+x$ 在 ${\mathbb{F}}_5$ 上的点计数

设 $E:y^2=x^3+x$ ， $q=5$ 。

逐点检验 $x=0,1,2,3,4$ ：

$x$	$x^3+x(\mathrm{mod}5)$	平方？	$y$ 的解
$0$	$0$	$0^2=0$	$y=0$ （1 个点 $(0,0)$ ）
$1$	$2$	不是平方	无
$2$	$10\equiv 0$	$0^2=0$	$y=0$ （1 个点 $(2,0)$ ）
$3$	$30\equiv 0$	$0^2=0$	$y=0$ （1 个点 $(3,0)$ ）
$4$	$68\equiv 3$	不是平方	无

加上无穷远点 $O$ ： $N_1=|E({\mathbb{F}}_5)|=4$ 。

由 Hasse 界： $|N_1-(q+1)|\le 2\sqrt{q}$ ，即 $|4-6|=2\le 2\sqrt{5}\approx 4.47$ 。✓

$E$ 的 trace of Frobenius： $a=q+1-N_1=5+1-4=2$ 。

Zeta 函数： $Z(E,t)=\frac{1-at+q{t}^2}{(1-t)(1-qt)}=\frac{1-2t+5t^2}{(1-t)(1-5t)}$ 。

验证 Weil 猜想 (iii)： $1-2t+5t^2$ 的根 $t=(2\pm \sqrt{4-20})/10=(2\pm 4i)/10$ 。 $|t|=1/\sqrt{5}=q^{-1/2}$ 。✓

例 同一条曲线在不同 ${\mathbb{F}}_{q^r}$ 上的点数

继续 $E:y^2=x^3+x$ 。 $N_r$ 由 Zeta 函数决定：

$$N_r=q^r+1-{\alpha }^r-{\overline{\alpha }}^r$$

其中 $\alpha ,\overline{\alpha }=1\pm 2i$ （ $1-2t+5t^2=(1-\alpha t)(1-\overline{\alpha }t)$ ， $\alpha =1+2i$ ）。

$r$	${\alpha }^r+{\overline{\alpha }}^r$	$N_r=5^r+1-({\alpha }^r+{\overline{\alpha }}^r)$
$1$	$2$	$6-2=4$ ✓
$2$	$(1+2i{)}^2+(1-2i{)}^2=2(1-4)=-6$	$26+6=32$
$3$	${\alpha }^3+{\overline{\alpha }}^3=2\cdot \mathrm{Re}((1+2i{)}^3)=2(-11)=-22$	$126+22=148$

关键观察：知道了 $\alpha$ （即 $E$ 的 Frobenius 的特征值，见 §10.2），就完全知道了所有 $N_r$ 。这是 Weil 猜想的核心推论——有限域上簇的全部算术信息被压缩在有限个特征值中。

直觉 Weil 猜想的意义

Weil 猜想是有限域上代数几何的基石。它们将有限域上簇的点计数与拓扑（上同调）联系起来。

• (i) 的证明（Dwork，1960）用 $p$ -adic 分析。
• (ii) 和 (iii) 的证明（Deligne，1974，Fields 奖）建立了 étale 上同调理论。

对于椭圆曲线，Weil 猜想退化为 Hasse 定理： $|N_1-(q+1)|\le 2\sqrt{q}$ 。这已被广泛用于椭圆曲线密码学——我们需要知道曲线群的精确阶以保证安全性。

Galois 理论联系：Frobenius 自同构（§10.2）是 Weil 猜想证明的核心角色。椭圆曲线的 Galois 表示 ${\rho }_{\ell }:\mathrm{Gal}(\overline{\mathbb{Q}}/\mathbb{Q})\to {\mathrm{GL}}_2({\mathbb{Z}}_{\ell })$ （来自 $\ell$ -adic 上同调）将 Frobenius 映射到特征多项式 $1-at+q{t}^2$ 的矩阵——这正是 Langlands 纲领（§12.8）的起点。

---

10.3.4 分圆多项式在有限域上的分解

定理 10.3.4 设 $gcd(q,n)=1$ ， $f={\mathrm{ord}}_n(q)$ （ $q$ 模 $n$ 的阶，即 $f=min\{k>0:q^k\equiv 1(\mathrm{mod}n)\}$ ）。则 ${\mathrm{\Phi }}_n(x)$ 在 ${\mathbb{F}}_q[x]$ 中分解为 $\phi (n)/f$ 个互异的 $f$ 次不可约多项式。

证明.${\mathrm{\Phi }}_n$ 的根是 $n$ 次本原单位根。在 ${\mathbb{F}}_{q^f}$ 中， $n\mid (q^f-1)$ ，故本原 $n$ 次单位根 ${\zeta }_n$ 存在。 ${\zeta }_n$ 在 ${\mathbb{F}}_q$ 上的极小多项式次数为 $f$ （因为 ${\zeta }_n,{\zeta }_n^q,{\zeta }_n^{q^2},\dots ,{\zeta }_n^{q^{f-1}}$ 恰好给出 $f$ 个互异共轭——它们恰好是 ${\zeta }_n$ 在 Frobenius 作用下的轨道）。 ${\mathrm{\Phi }}_n$ 的 $\phi (n)$ 个根被分成 $\phi (n)/f$ 个 Frobenius 轨道，每个轨道给出一个 $f$ 次不可约因子。 $◻$

例 具体的分圆多项式分解

例 1： ${\mathrm{\Phi }}_7(x)$ 在 ${\mathbb{F}}_2$ 上。

$\phi (7)=6$ 。 $2$ 模 $7$ 的阶： $2^1=2,2^2=4,2^3=1(\mathrm{mod}7)$ 。 $f=3$ 。

${\mathrm{\Phi }}_7(x)=x^6+x^5+x^4+x^3+x^2+x+1$ 分解为 $6/3=2$ 个 $3$ 次不可约多项式。

验证： ${\mathbb{F}}_2$ 上 $3$ 次不可约多项式只有 $x^3+x+1$ 和 $x^3+x^2+1$ 。 $(x^3+x+1)(x^3+x^2+1)=x^6+x^5+x^4+x^3+x^2+x+1={\mathrm{\Phi }}_7(x)$ 。✓

例 2： ${\mathrm{\Phi }}_{15}(x)$ 在 ${\mathbb{F}}_2$ 上。

$\phi (15)=8$ 。 $2$ 模 $15$ 的阶： $2^1=2,2^2=4,2^3=8,2^4=16\equiv 1(\mathrm{mod}15)$ 。 $f=4$ 。

${\mathrm{\Phi }}_{15}(x)$ 分解为 $8/4=2$ 个 $4$ 次不可约多项式。

${\mathrm{\Phi }}_{15}(x)=x^8+x^7+x^5+x^4+x^3+x+1=(x^4+x+1)(x^4+x^3+1)$ 。

例 3： ${\mathrm{\Phi }}_5(x)$ 在 ${\mathbb{F}}_2$ 上。

$\phi (5)=4$ 。 $2^1=2,2^2=4,2^3=3,2^4=1(\mathrm{mod}5)$ 。 $f=4$ 。

${\mathrm{\Phi }}_5(x)=x^4+x^3+x^2+x+1$ 。 $4/4=1$ 个不可约因子。即 ${\mathrm{\Phi }}_5$ 本身在 ${\mathbb{F}}_2$ 上不可约。✓

例 4： ${\mathrm{\Phi }}_5(x)$ 在 ${\mathbb{F}}_4$ 上。

$q=4$ ， $4^1=4\equiv 4,4^2=16\equiv 1(\mathrm{mod}5)$ 。 $f=2$ 。

${\mathrm{\Phi }}_5(x)$ 在 ${\mathbb{F}}_4$ 上分解为 $4/2=2$ 个 $2$ 次不可约多项式。

对比：同一个 ${\mathrm{\Phi }}_5$ ，在 ${\mathbb{F}}_2$ 上不可约（ $f=4$ ），在 ${\mathbb{F}}_4$ 上分解为 2 个二次因子（ $f=2$ ），在 ${\mathbb{F}}_5$ 上...等等， $gcd(5,5)=1$ 不成立，此时 ${\mathrm{\Phi }}_5(x)=(x-1{)}^4$ （有重根，不可分）。

注 定理 10.3.4 与 Frobenius 的联系

定理的证明本质上只用了一个事实：Frobenius ${\sigma }_q$ 在 ${\mathbb{F}}_{q^f}/{\mathbb{F}}_q$ 的 Galois 群中生成整个群（见 §10.2）。 ${\zeta }_n$ 的极小多项式就是其 Frobenius 轨道的乘积。

这再次体现了有限域的核心美学：Galois 群是循环群，Frobenius 是生成元，所有结构都由 Frobenius 的作用决定。

本节知识检验

自测题：

1. 在 ${\mathbb{F}}_2[x]/(x^7-1)$ 中，取 $g(x)=x^3+x^2+1$ 。这生成什么参数的循环码？

2. 在 ${\mathbb{F}}_{11}^{\times }$ （ $g=2$ ）中，计算 ${\log }_2(7)$ 。

3. ${\mathrm{\Phi }}_{11}(x)$ 在 ${\mathbb{F}}_3$ 上如何分解？（提示： $3$ 模 $11$ 的阶是 $5$ 。）

4. 椭圆曲线 $E:y^2=x^3+x$ 在 ${\mathbb{F}}_3$ 上有多少个有理点？

5. 为什么 AES 选择 ${\mathbb{F}}_{2^8}$ 而不是 ${\mathbb{F}}_{2^{16}}$ 或 ${\mathbb{F}}_{101}$ ？

答案要点：

1. $g(x)\mid (x^7-1)$ ， $\mathrm{deg}g=3$ ， $[7,4,d{]}_2$ 码。 $d$ 取决于 $g$ 的具体选择，对 $g=x^3+x^2+1$ ， $d=3$ （Hamming 码）。

2. 查表： $2^7=128=11\cdot 11+7\equiv 7(\mathrm{mod}11)$ 。 ${\log }_2(7)=7$ 。

3. $\phi (11)=10$ ， $f=5$ （ $3^5=243=22\cdot 11+1$ ）。 ${\mathrm{\Phi }}_{11}$ 分解为 $10/5=2$ 个 $5$ 次不可约多项式。

4. 逐点检验： $x=0$ : $y^2=0$ , $(0,0)$ 。 $x=1$ : $y^2=2$ , ${\mathbb{F}}_3$ 中 $2$ 不是平方，无解。 $x=2$ : $y^2=10\equiv 1$ , $y=1,2$ , 两个点 $(2,1),(2,2)$ 。加上 $O$ : $N_1=4$ 。Hasse 界： $|4-4|=0\le 2\sqrt{3}\approx 3.46$ 。✓

5. 字节对齐（ $2^8=256$ 对应一个字节）， ${\mathbb{F}}_{2^8}$ 上的乘法可以用移位和 XOR 高效实现。 ${\mathbb{F}}_{101}$ 不是 2 的幂，无法自然映射到字节。 ${\mathbb{F}}_{2^{16}}$ 的乘法表太大（ $2^{16}\times 2^{16}$ ），硬件实现不经济。

---

常见误区

误区一：线性码是"任意子集"

线性码 $C$ 是 ${\mathbb{F}}_q^n$ 的子空间，不是任意子集。这意味着：

• 零向量 $\mathbf{0}$ 总在 $C$ 中（所以最小距离 $d$ 不是"码字间的最小距离"，而是非零码字的最小重量）。
• 两个码字的和仍是码字（线性性使得编码和译码可以用矩阵运算高效实现）。
• $|C|=q^k$ （ $k$ 是维数），所以信息位数恰好是 $k$ 。

非线性码（如某些最优码）不满足这些性质，但线性码在实际中占主导地位，因为矩阵运算比一般集合运算高效得多。

误区二：Reed-Solomon 码在实数域上也能工作

RS 码的构造依赖于 ${\mathbb{F}}_q$ 上的有限性质：

• 译码需要在 ${\mathbb{F}}_q$ 上做多项式插值，而 ${\mathbb{F}}_q$ 上的插值是精确的（没有舍入误差）。
• 码字的每个分量是 ${\mathbb{F}}_q$ 的元素（有限个可能值），适合数字传输。
• 距离界 $d=n-k+1$ 依赖于" $n$ 次多项式至多有 $n$ 个根"，这在任意域上成立，但实际编码需要有限域来保证码字是有限长的符号串。

在实数域上，多项式插值的系数是无理数，无法精确存储和传输。

误区三：离散对数问题"只是"求对数

离散对数 ${\log }_g(h)=x$ （ $g^x=h$ ）在 ${\mathbb{F}}_q^{\times }$ 中的计算复杂度与经典对数完全不同：

• 经典对数（如 $\ln 2$ ）可以用泰勒级数快速逼近。
• 离散对数没有已知的多项式时间经典算法（最好的算法如 index calculus 仍是亚指数的）。
• 但在量子计算机上，Shor 算法可以在多项式时间内解决离散对数问题。

这就是为什么基于离散对数的密码系统（如 Diffie-Hellman）在量子计算时代需要被后量子密码替代。

---

10.3.5 与前面章节的联系

本节的应用全部建立在有限域的结构定理之上：

应用	核心依赖	章节
循环码 $\leftrightarrow$ 理想	${\mathbb{F}}_q[x]$ 是主理想环	§2.2, §2.3
RS 码的距离最优	多项式插值（根的个数）	§4.1
离散对数	${\mathbb{F}}_q^{\times }$ 是循环群	§10.1
AES 字节替换	${\mathbb{F}}_{2^8}$ 中求逆	§10.1
Weil 猜想	Frobenius 自同构	§10.2
分圆多项式分解	Frobenius 轨道	§10.2
椭圆曲线点计数	Galois 特征值	§10.2

注 向前看

有限域的应用远不止本节所述：

• 编码理论的深入需要 第十一章 的无限 Galois 理论（代数几何码）。
• 椭圆曲线密码学的理论基础是 §12.8 的 Langlands 纲领。
• 代数几何码（Goppa 码）使用代数曲线上的函数域，连接了编码理论和算术几何。
• 量子计算中的量子纠错码（如 stabilizer codes）使用 ${\mathbb{F}}_2$ 上的辛几何。

---

← [§10.2 Frobenius 自同构](/chapters/10-finite-fields/10.2-frobenius)[第十一章 · 无限 Galois 理论 →](/chapters/11-infinite-galois/)