有限域基础知识

有限域的基本结构与性质

特征与基域

回顾域论基础，对于有限域 $F$：

• 特征 (Characteristic)：有限域的特征 $char(F) = p$，其中 $p$ 为素数。
• 基域：$F$ 必定包含一个同构于 $\mathbb{Z}_p$ 的素域，这里记为 $F_{p}$
  • 即 $F_{p}<F$，有时候也可以简单的写为 $\mathbb{Z}_p < F$
• 乘法群：有限域的非零元乘法群 $(F^*, \cdot)$ 是循环群。

扩张与阶

设 $F$ 是有限域，其代数扩张 $E / F$ 具有以下性质：

1. 可分性：有限域的代数扩张都是可分的（Separable）。
2. 单代数扩张：对于某个 $\alpha \in E$，有 $E = F(\alpha)$
   • 这一点可以利用 $(E^{*}, \cdot )$ 是循环群证明
3. 维数与元素个数：
   • 假如 $[E:F] = n$，取 $E$ 在 $F$ 上的一组基 $\alpha_1, \ldots \alpha_n$
   • $E$ 上任意元素可以表示为 $\sum_{i=1}^{n}a_i \alpha_i$，其中 $a_i \in F$
   • 因此有 $\left\vert E \right\vert = \left\vert F \right\vert^{n}$
   • 考虑到上面的 $char(F) = p \Rightarrow \mathbb{Z}_{p}<F$，那么应当有 $\left\vert F \right\vert = p^{n}$

记号约定：

• 通常记 $q = p^n$。
• 有限域记为 $F_q$ 或 $GF(q)$，其中 $|F_q| = q$。

有限域都是分裂域

性质
有限域 $F_q$ 可以被刻画为多项式 $x^q - x$ 的在素域 $\mathbb{Z}_{p}$ 上的分裂域。

根的性质：

• $F_q$ 中的所有非零元素构成阶为 $q-1$ 的循环群，即 $\forall \alpha \in F_q^*, \alpha^{q-1} = 1$。
• 加上零元素，则 $\forall \alpha \in F_q, \alpha^q = \alpha$。
• 这意味着 $F_q$ 的所有元素都是方程 $x^q - x = 0$ 的根。

重根判定：
考虑多项式 $f(x) = x^q - x$，其导数为：

$$f'(x) = qx^{q-1} - 1 = -1 \neq 0 \quad (\text{在特征 } p \text{ 的域中 } q=p^n=0)$$

由于导数不为 0 且与 $f(x)$ 互素，故 $x^q - x$ 没有重根。其根的集合大小恰好为 $q$，从而得到根的集合恰好为 $F_q$

利用多项式构造有限域：唯一性

前面我们知道假如 $\left\vert F \right\vert = q$，那么 $\exists n, p$ 使得 $q = p^{n}$。接下来我们考虑：是否对于任意的 $n$，得到的 $q = p^{n}$ 都能是某个有限域的大小？事实上，可以通过构造法证明阶为 $q = p^{n}$ 的有限域对于 $\forall n$ 存在且是唯一的。

命题：
考虑 $q = p^{n}, n \in \mathbb{N}^{*}$，令 $F$ 为多项式 $x^q - x \in \mathbb{Z}_{p}[x]$ 在其代数闭包中的所有根的集合，则 $F$ 构成一个域。

注：由于同一个多项式在不同的代数闭包下可能有不同的根（特征不同导致根不同），因此这里需要先承接 $F_q$ 有一个子域 $\mathbb{Z}_p$ 的思路，先构造出 $\mathbb{Z}_p$，然后再在其代数闭包上求根。

证明：

1. 减法封闭性：
   对任意 $\alpha, \beta \in F$，考察 $\alpha - \beta$：

   $$(\alpha - \beta)^q - (\alpha - \beta) = (\alpha^q - \beta^q) - (\alpha - \beta) = (\alpha - \alpha) - (\beta - \beta) = 0$$

   故 $\alpha - \beta \in F$。

2. 除法封闭性：
   对任意 $\alpha \in F, \beta \in F \setminus \{0\}$，考察 $\alpha \beta^{-1}$：

   $$(\alpha \beta^{-1})^q - \alpha \beta^{-1} = \alpha^q (\beta^q)^{-1} - \alpha \beta^{-1} = \alpha \beta^{-1} - \alpha \beta^{-1} = 0$$

   故 $\alpha \beta^{-1} \in F$。

得到 $F$ 是一个域，且 $|F|=q$。考虑到 $x^{q} - x$ 的根在代数闭包中是唯一的，因此 $F_{q}$ 是唯一的。

结论：

• 结构链：$F_p \cong \mathbb{Z}_p < F_q = F_{p^n}$
• $F_{q}<F_{q^{n}}$，且 $F_{q^{n}}$ 是 $F_q$ 上的分裂域（从前面推导可以看出，基域的大小不重要）

有限域的子域结构

定义 (定义多项式)：
考虑结构形如 $x^{q^{d}} - x$ 的多项式，记为 $f_{q^{d}}(x)$，称为定义多项式。

包含关系判定

考虑扩张 $F_q < F_{q^n}$。更一般地，对于 $F_{q^k}$ 和 $F_{q^n}$，何时满足 $F_{q^k} \subseteq F_{q^n}$？

结论
$F_{q^k} \subseteq F_{q^n} \iff f_{q^{k}}(x) \mid f_{q^{n}}(x) \iff k \mid n$。

证明思路：
考察 $x^n - 1$ 的整除性。设 $n = mk + r$，其中 $0 \le r < k$。

$$\begin{aligned} x^{n} - 1 &= x^{mk+r} - 1 \\ & = x^{mk+r} - x^{(m-1)k + r} + x^{(m-1)k + r} - 1 \\ & = x^{(m-1)k+r}(x^{k}-1) + x^{(m-1)k + r} - 1 \end{aligned}$$

根据上式，有 $x^{k} - 1 \mid x^{n} - 1 \iff x^{k} - 1 \mid x^{(m-1)k + r} - 1$，相当于给被除数的 $x$ 降了 $k$ 的系数，因此：

$$\begin{aligned} x^{k} - 1 \mid x^{n} - 1 &\iff x^{k} - 1 \mid x^{(m-1)k + r} - 1 \\ &\iff x^{k} - 1 \mid x^{(m-2)k + r} - 1 \iff \cdots \\ &\iff x^{k} - 1 \mid x^{r} - 1 \end{aligned}$$

但是 $0\le r<k$，因此 $r = 0$，即 $k \mid n$

利用上述结论，考察 $F_{q^{d}}, F_{q^{n}}$

$$\begin{aligned} d \mid n &\iff x^{d} - 1 \mid x^{n} -1 \iff q^{d} -1 \mid q^{n} - 1 \\ &\iff x^{q^{d}-1} -1 \mid x^{q^{n}-1} -1 \iff x^{q^{d}} -x \mid x^{q^{n}}-x \\ &\iff Roots(f_{q^{d}}(x)) \subseteq Roots(f_{q^{d}}(x)) \iff F_{q^{d}} \subseteq F_{q^{n}} \end{aligned}$$

令 $f_{q^k}(x) = x^{q^k} - x$，则上述整除关系意味着 $F_{q^k}$（即 $f_{q^k}(x)$ 的根集）包含在 $F_{q^n}$（即 $f_{q^n}(x)$ 的根集）中。

注：
注意到最大公因数与域无关，因此对于 $f_{q^{d}}(x) \mid f_{q^{n}}(x)$ 这个整除关系，由于函数 $f$ 的系数非常简单，因此在最简单的 $\mathbb{Z}_p$ 域上，整除依然成立。

例子

例：考察 $F_{1024}$ 的所有子域

$$F_{1024} = F_{2^{10}}$$

首先子域的特征不会变，依然是 $2$，因此子域大小为 $2^{n}$ 的形式。有前述判定方法可知，子域为 $F_{2}, F_{2^{2}}, F_{2^{5}}, F_{2^{10}}$

有限域的 Galois 理论

Galois 群结构

考虑有限扩张 $F_{q^n} / F_q$。这是一个 Galois 扩张，其 Galois 群记为 $G = Gal(F_{q^n}/F_q)$。
已知扩张次数 $[F_{q^n} : F_q] = n$，故 Galois 群的大小 $|G| = n$。

Frobenius 自同构：
定义映射 $\sigma: F_{q^n} \to F_{q^n}$，$\sigma(\alpha) = \alpha^q$。
考虑 $\forall \alpha \in F_q$，发现 $\sigma(\alpha) = \alpha ^{q} = \alpha$，即 $\sigma$ fixes $F_q$，可知 $\sigma \in G$。

考察 $\sigma^{n}$
$\forall \alpha \in F_{q^{n}}$，有 $\sigma^{n}(\alpha) = \alpha^{q^{n}} = \alpha$，即 $\sigma^{n}$ 为恒等映射，$\sigma^{n} = \iota = \sigma^{0}$

证明 $G$ 是循环群：
首先证明 $\sigma$ 生成的子群形式为 $\langle \sigma \rangle = \{ \sigma^0, \sigma^1, \dots, \sigma^{n-1} \}$，即证集合中每一个元素都不同。利用反证法：

• 若存在 $k < n$ 使得 $\sigma^k = id$，则 $\forall \alpha \in F_{q^n}, \alpha^{q^k} = \alpha$，即 $\alpha^{q^k} - \alpha = 0$。
• 方程 $x^{q^k} - x = 0$ 最多有 $q^k$ 个根，但 $F_{q^n}$ 有 $q^n$ 个元素。
• 当 $k < n$ 时，$q^k < q^n$，导致矛盾。

因此 $\left\vert \langle \sigma \rangle \right\vert = n = \left\vert G \right\vert$，同时 $\sigma \in G \Rightarrow \langle \sigma \rangle\subseteq G$，得到 $G = \langle \sigma \rangle$

结论：$Gal(F_{q^n}/F_q) = \langle \sigma \rangle \cong \mathbb{Z}_n$。

不可约多项式与元素的阶

不可约多项式的存在性

对于任意 $d > 0$，在 $F_q$ 上是否存在次数为 $d$ 的不可约多项式？答案是肯定的。
构造方法：

1. 考虑扩张 $F_{q^d}$。
2. $F_{q^d}$ 是 $F_q$ 上的 $d$ 次扩张，即 $[F_{q^d} : F_q] = d$。
3. 存在本原元（Simple extension generator）$\alpha$ 使得 $F_{q^d} = F_q(\alpha)$。
4. 令 $p(x)$ 为 $\alpha$ 在 $F_q$ 上的极小多项式，则 $\deg(p(x)) = d$ 且 $p(x)$ 不可约。

阶 (Order) 的性质

对于 $\alpha \in F_{q^n}^*$，定义其阶 $ord(\alpha)$ 为使得 $\alpha^v = 1$ 的最小正整数 $v$。

共轭根的阶相同：

• 设 $p(x)$ 是 $F_q$ 上的不可约多项式，记分裂域为 $F_{q^{d}}$
• 考虑 $p(x)$ 的两个根 $\alpha, \beta$，有：$F_{q^{d}} = F_q(\alpha) = F_q(\beta)$（可以利用有限域的唯一性理解）
• 假设 $ord(\alpha) = v$，即 $\alpha ^{v} = 1$
• 根据代数扩张的嵌入延展定理，存在嵌入 $\sigma: F(\alpha) \hookrightarrow \bar{F}$ 的 $F$-嵌入，使得 $\sigma(\alpha) = \beta$。
• 可以发现 $\sigma(F(\alpha)) = F(\sigma(\alpha)) = F(\beta) = F(\alpha)$，这里其实就是正规扩张的性质，同时也说明 $\sigma$ 是 $F(\alpha)$ 的 $F$-自同构
• 因此 $\beta ^{v} = \sigma(\alpha)^{v} = \sigma(\alpha ^{v}) = 1$
• 反之，如果 $\beta ^{v} = 1 \Rightarrow \alpha ^{v}=1$，得到 $ord(\beta) = ord(\alpha)$
• 即不可约多项式的所有根具有相同的阶。

定义 (多项式的阶)
由于不可约多项式 $p(x)$ 定义为其任一根 $\alpha$ 的阶。

不可约多项式度与阶的关系

考虑 $F_q$ 上的极小多项式 $p(x)$ 次数为 $d$，阶为 $v$，那么任一根 $\alpha$ 的阶也为 $v$
我们已知 $\alpha \in F_{q^d}$，这意味着：

$$\alpha^{q^d} = \alpha \iff \alpha^{q^d - 1} = 1$$

结合 $\alpha ^{v} = 1$，必有：

$$v \mid q^d - 1 \implies q^d \equiv 1 \pmod v$$

实际上，$d$ 是使得上述同余式成立的最小正整数。即 $d$ 是 $q$ 模 $v$ 的乘法阶 (Multiplicative order of $q$ modulo $v$)。
证明 ($d$ 是最小的)

• 同样使用反证法，假设 $k<d$ 且 $v \mid p^{k} - 1$
• 那么 $\alpha ^{v} = 1 \Rightarrow \alpha ^{q^{k}-1} = 1\Rightarrow \alpha ^{q^{k}} - \alpha = 0$
• $\alpha$ 是 $x^{q^{k}}-x$ 的根，$\alpha \in F_{q^{k}}$
• 从而 $F_q(\alpha) \subseteq F_{q^{k}}$，与 $F_q(\alpha) = F_{q^{d}}$ 矛盾

本原多项式

定义 (本原多项式)
如果 $\alpha$ 是 $F_{q^n}^*$ 的生成元（本原元），则 $ord(\alpha) = q^n - 1$。此时 $\alpha$ 在 $F_q$ 上的极小多项式称为本原多项式 (Primitive Polynomial)。本原多项式的阶为 $q^n - 1$。

上述极小多项式在代数编码理论中很有用。

算法与应用：计算多项式的阶

在找到本原多项式之前，先考虑一个问题：给定 $F_q$ 上的 $d$ 次不可约多项式 $p(x)$，如何计算其阶（即 $p(x)$ 的根的阶 $v$）？

已知条件：

1. $v \mid q^d - 1$。
2. $\alpha ^{v} = 1 \Rightarrow p(x) \mid x^{v} - 1$

计算策略：
我们需要找到最小的 $v$ 使得 $p(x) \mid x^v - 1$（等价于 $x^v \equiv 1 \pmod{p(x)}$）。
这可以通过检查 $q^d - 1$ 的因子来实现。

算法步骤：

1. 计算最大可能的周期 $N = q^d - 1$。
2. 对 $N$ 进行素因子分解：$N = p_1^{e_1} p_2^{e_2} \dots p_m^{e_m}$。
3. 对于每个素因子 $p_i$，检查 $x^{N/p_i} \pmod{p(x)}$ 是否为 1：
   • 如果对于某个 $p_i$，有 $x^{N/p_i} \equiv 1 \pmod{p(x)}$，说明真正的阶 $v$ 是 $N/p_i$ 的因子。
   • 此时令 $N \leftarrow N/p_i$，重复检查。
   • 如果对于所有的 $p_i$，都有 $x^{N/p_i} \not\equiv 1 \pmod{p(x)}$，则当前的 $N$ 即为所求的阶 $v$。

实例分析

例：考察 $F_2$ 上的多项式 $p(x) = x^6 + x + 1$。
这里 $q=2, d=6$。

1. 计算最大周期：$N = 2^6 - 1 = 63$。
2. 分解 $N$：$63 = 3^2 \cdot 7$。素因子为 $3, 7$。
3. 我们需要检查 $N/3 = 21$ 和 $N/7 = 9$：
   • 计算 $x^{21} \pmod{x^6+x+1}$。
   • 计算 $x^9 \pmod{x^6+x+1}$。
4. 若以上结果均不为 1，则 $p(x)$ 的阶为 63，即它是一个本原多项式。

(注：此例对应教材 Example 9.6.1)