第 12 讲：有限域、不可约多项式与周期

有限域的特征是素数 $p$，把它看成素域 $\mathbb F_p$ 上的有限维线性空间，若维数为 $n$，元素个数就是 $p^n$。反过来，对每个素数幂 $q=p^n$，都存在 $q$ 元域，而且同阶有限域彼此同构。

因此不存在 $6$ 元域、$10$ 元域或 $12$ 元域，因为这些数都不是单个素数的幂。$\mathbb Z_n$ 是域当且仅当 $n$ 为素数；当需要 $p^n$ 且 $n>1$ 个元素时，不能直接把整数模 $p^n$，而要用不可约多项式扩张。

有限域乘法群 $\mathbb F_q^\times$ 是阶为 $q-1$ 的循环群。因此每个非零元素满足 $a^{q-1}=1$，所有元素满足 $a^q=a$，从而

$$x^q-x=\prod_{a\in\mathbb F_q}(x-a).$$

映射

$$\operatorname{Fr}:a\mapsto a^p$$

称为 Frobenius 自同构。在特征 $p$ 下，二项式中间系数都被 $p$ 整除，所以

$$(a+b)^p=a^p+b^p.$$

在 $\mathbb F_{p^n}$ 上反复作用 $n$ 次得到 $a^{p^n}=a$。

用不可约多项式构造

取 $\mathbb F_p$ 上 $n$ 次不可约多项式 $f$，则

$$\mathbb F_p[x]/(f)$$

是 $p^n$ 元域。它的元素可写成次数小于 $n$ 的多项式，乘法后对 $f$ 取余。

更一般地，$\mathbb F_q$ 上所有次数整除 $n$ 的首一不可约多项式，恰好各出现一次地乘成 $x^{q^n}-x$。这既能枚举低次不可约多项式，也能判断某个不可约多项式的根落在哪个扩域。

例：构造四元域

$x^2+x+1$ 在 $\mathbb F_2$ 上没有根，所以不可约。令

$$\alpha=x+(x^2+x+1),$$

则

$$\mathbb F_4 =\mathbb F_2[x]/(x^2+x+1) =\{0,1,\alpha,\alpha+1\},$$

并有

$$\alpha^2+\alpha+1=0, \qquad \alpha^2=\alpha+1.$$

于是

$$\alpha(\alpha+1) =\alpha^2+\alpha=1,$$

所以 $\alpha^{-1}=\alpha+1$。继续算得 $\alpha^3=1$，非零三个元素组成循环群。

有限域 $\mathbb F_{p^n}$ 的子域也受次数约束：它含有同构于 $\mathbb F_{p^d}$ 的子域，当且仅当 $d\mid n$；而且对每个这样的 $d$，子域唯一。

周期与本原多项式

设 $f\ne x$ 是 $n$ 次不可约多项式。它的周期是最小正整数 $e$，使

$$f(x)\mid x^e-1.$$

等价地，$e$ 是 $x+(f)$ 在商域乘法群中的阶，所以 $e\mid q^n-1$。若 $e=q^n-1$，则 $f$ 是本原多项式。判断时只需对 $q^n-1$ 的各个素因子 $r$ 检查 $x^{(q^n-1)/r}\not\equiv1\pmod f$。

不可约不自动等于本原。不可约只保证商结构是域；本原还要求 $x+(f)$ 恰好生成整个乘法群。判断流程是：

1. 先证明 $f$ 不可约；
2. 分解 $q^n-1$；
3. 对每个不同素因子 $r$ 计算 $x^{(q^n-1)/r}\bmod f$；
4. 这些余数都不为 $1$，才说明元素阶没有落在任何真因子上。

在四元域例子中 $q^n-1=3$，而 $\alpha\ne1$、$\alpha^3=1$，所以 $\alpha$ 的阶为 $3$，$x^2+x+1$ 同时也是 $\mathbb F_2$ 上的本原多项式。