域论

前置知识：抽象代数基本概念、群论、环论

引入

域论（field theory）是关于域的理论。

本文涉及的域论主要是域的扩张理论。域是对加、减、乘、除都封闭的代数结构，算法竞赛中经常需要对质数 $p$ 取模，就相当于在有限域 ${\mathbf{F}}_p$ 上进行运算。和实数域 $\mathbf{R}$ 的情形类似，有些问题的求解在更大的域（即复数域 $\mathbf{C}$）上进行计算更为方便，常见的例子比如利用 快速傅里叶变换 加速实系数多项式的乘法。对于有限域也可以做类似的操作。多数读者对于有限域的扩张相对陌生，因而，了解一般的域上的扩张理论是有益的。文末给出了一些需要对有限域进行扩张的算法应用，同时也简单地讨论了部分应用中可能需要的整数环上的扩张。

与域论紧密相关的是 Galois 理论。它将域的扩张与其自同构群联系起来，从而可以通过群论的工具来理解域的扩张的性质。尽管这一理论也往往是相关代数课程的核心内容，但是与算法竞赛的内容相去甚远，故而本文不做过多介绍。有兴趣的读者应当阅读相关专业书籍。

记号

在不引起歧义时，本文可能会省略掉环和域的乘法记号，并且会将环 $(R,+,\cdot )$ 写作环 $R$，将域 $(F,+,\cdot )$ 写作域 $F$。环和域的加法单位元称为零元，乘法单位元称为幺元。而且，本文中的 $p$ 总是素数，而 $q$ 总是素数幂，且可以写作 $p^n$，其中，$n$ 是正整数。

域的扩张

类似群、环的情形，可以建立子域和域同态的概念。

子域

对于域 $F$，如果它的子环 $E$ 也是域，那么称 $E$ 是域 $F$ 的 子域（subfield）。

其中，无论环和子环的定义对于幺元的处理如何，子域 $E$ 必然包含域 $F$ 的幺元 ¹。

域同态

自域 $F$ 到域 $E$ 的环同态 $\phi :F\to E$ 也称为自域 $F$ 到域 $E$ 的 域同态（field homomorphism）。

域同态对幺元的处理

如果与本文的定义不同，环同态要求幺元映射到幺元，那么域同态自然也要求幺元映射到幺元。否则，幺元也可能映射到零元。

因为域只有平凡的理想，所以域同态要么将整个域映射到零元，要么必然是嵌入映射。这说明，域同态的讨论可以转化为子域的讨论。

在域的情形，往往更小的域是更为熟悉的域，所以，通常会转而以子域作为基点来考察更大的域。这就是域的扩张的概念。

域扩张

对于域 $F$，如果 $F$ 是 $E$ 的子域，则称域 $E$ 是域 $F$ 的 扩张（extension），或称 扩域，记作 $E/F$。

域扩张的记号

尽管形式上一致，但是域扩张的概念和商环并没有关系，不应混淆。

例子

复数域 $\mathbf{C}$ 就是实数域 $\mathbf{R}$ 的扩张，而实数域 $\mathbf{R}$ 又是有理数域 $\mathbf{Q}$ 的扩张。

域扩张的次数

对于域扩张 $E/F$，域 $E$ 总是域 $F$ 上的 线性空间。这个线性空间的维度就是域扩张的次数。

域扩张的次数

域扩张 $E/F$ 的 次数（degree），是指将 $E$ 看作是域 $F$ 上线性空间时的维度，即 ${\dim }_F(E)$，记作 $[E:F]$。如果域扩张的次数是有限的，就称域扩张为 有限扩张（finite extension），否则就称为 无限扩张（infinite extension）。

例子

域扩张 $\mathbf{C}/\mathbf{R}$ 的次数 $[\mathbf{C}:\mathbf{R}]$ 等于 $2$，所以是有限扩张。域扩张 $\mathbf{R}/\mathbf{Q}$ 是无限扩张。

域的扩张次数满足乘法原理。

定理

设 $F\subseteq K\subseteq E$ 都是域，则它们之间的扩张次数满足 $[E:F]=[E:K][K:F]$。

证明

对于扩张次数是无限的情形，这是显然的；否则，如果 $\{{\alpha }_i\}$ 是 $E$ 作为 $K$ 上线性空间的一组基，且 $\{{\beta }_j\}$ 是 $K$ 作为 $F$ 上线性空间的一组基，那么可以验证，$\{{\alpha }_i{\beta }_j\}$ 是 $E$ 作为 $F$ 上线性空间的一组基。

本文讨论的情形主要是域的有限扩张。

域的特征

对域扩张的研究，有一个自然的起点，就是包含域 $F$ 幺元的最小子域，这个域也称为域 $F$ 的 素子域（prime subfield）。

素子域的结构，由域幺元的性质唯一确定。域的特征就概括了这样的性质。

域的特征

域 $F$ 的 特征（characteristic）是使得 $n\cdot 1=0$ 成立的最小正整数 $n$；如果这样的 $n$ 不存在，则称域 $F$ 的特征是 $0$。其中，$n\cdot 1$ 指 $n$ 个幺元 $1$ 相加的结果。如果域 $F$ 的特征不为 $0$，那么就称域 $F$ 是 有限特征的（finite characteristic）。

域的特征可以通过环同态来理解。整数环 $\mathbf{Z}$ 就是自 $0$ 和 $1$ 出发，反复施加加、减、乘等运算得到的封闭结构。它可以看作某种「原型」，所有包含幺元的环都应当「继承」了整数环的部分结构 ²。因而，对于域 $F$，可以考察环同态 $\phi :\mathbf{Z}\to F$ 并要求 $\phi (1)=1$。这样的环同态是唯一确定的，它将 $n\in {\mathbf{N}}_{+}$ 映射到 $n\cdot 1$，即 $n$ 个幺元 $1$ 相加。该同态的像 $\phi (\mathbf{Z})$ 嵌入了域 $F$ 中，必然含幺、交换、无零因子，故而是整环。所以，同态的核 $\ker \phi$ 必然是素理想。整数环 $\mathbf{Z}$ 的素理想只能是 $(n)$ 的形式，其中 $n=0$ 或者 $n$ 是素数。这样得到的 $n$ 就是该域的特征。

域的特征确定了素子域的结构：

1. 当特征为 $0$ 时，同态 $\phi$ 是单的，整数环 $\mathbf{Z}$ 嵌入了域 $F$ 中。有理数域 $\mathbf{Q}$ 作为最小的包含整数环的域必然也可以嵌入域 $F$ 中，它就是域 $F$ 的素子域；
2. 当特征为素数 $p$ 时，同态 $\phi$ 的像 $\mathbf{Z}/p\mathbf{Z}$ 嵌入了域 $F$ 中。此时，$\mathbf{Z}/p\mathbf{Z}$ 已经是域，记作 ${\mathbf{F}}_p$，它就是域 $F$ 的素子域。

这些讨论实际上说明了如下结论：

定理

域 $F$ 的特征只能是 $0$ 或素数 $p$。特征为 $0$ 的域对应的素子域是 $\mathbf{Q}$，特征为素数 $p$ 的域对应的素子域是 ${\mathbf{F}}_p$。

定理中的 $\mathbf{Q}$ 和 ${\mathbf{F}}_p$ 也称为 素域（prime field），即子域只有它自身的域。有限域必然是有限特征的，因为特征为 $0$ 的域至少包含子域 $\mathbf{Q}$。

特征有限的域和零特征的域性质往往不同。比如，有限特征的域有如下性质：

定理

设 $F$ 的特征为 $p$，则有：

1. 域 $F$ 的加法群中，所有非零元素的阶都是 $p$，即对所有 $x\in F$ 都有 $px=0$；
2. 「新手之梦」（freshman’s dream），即对所有 $x,y\in F$ 都有 $(x+y{)}^p=x^p+y^p$。进而，映射 $x\mapsto x^p$ 是 $F$ 上的单自同态，叫做 Frobenius 自同态（Frobenius endomorphism）。

证明

对于第一条性质，只要注意到 $px=(p1)x=0x=0$ 即可。对于第二条性质，只需要注意到 $(x+y{)}^p$ 的二项式展开中，除了 $x^p$ 和 $y^p$ 外的全部其他项的系数都是 $p$ 的倍数，故而根据第一条性质就有 $(x+y{)}^p=x^p+y^p$。至于验证 $x\mapsto x^p$ 是自同态，只需要再验证 $(xy{)}^p=x^p{y}^p$，这是因为域的乘法满足交换律。最后，域之间的环同态将幺元映射到幺元，则必然是单射。

当然，对于有限域，Frobenius 自同态必然也是满的，因而是域的自同构。

单扩张

类似于实数域扩张到复数域的情形，很多扩张可以通过向域中添加额外的元素，并规定其运算性质来完成。在一般的情形，为避免规定运算性质引起的麻烦，不妨考虑在域扩张 $E/F$ 中，将 $E\setminus F$ 中的元素附加到 $F$ 上的情形，此时这些额外的元素与域 $F$ 中元素的运算的规则已经在更大的域 $E$ 中确定了。

由子集生成的域扩张

设 $E/F$ 是域扩张，$S\subseteq E$，那么 由 $S$ 生成的域 $F$ 上的扩张（extension generated by $S$ over $F$）就是指同时包含 $F$ 和 $S$ 的，最小的 $E$ 的子域，记作 $F(S)$。

最为简单的情形自然是集合 $S$ 中的元素很少的情形。

有限生成扩张

设 $E/F$ 是域扩张，如果存在有限集 $S=\{{\alpha }_1,\cdots ,{\alpha }_n\}\subseteq E$ 使得 $E=F(S)$ 成立，则称 $E$ 为域 $F$ 的 有限生成扩张（finitely generated extension），也记作 $F({\alpha }_1,\cdots ,{\alpha }_n)$。

单扩张

设 $E/F$ 是域扩张，如果存在 $\alpha \in E$ 使得 $E=F(\alpha )$ 成立，则称域 $E$ 是域 $F$ 的 单扩张（simple extension）。其中，元素 $\alpha$ 称为这个单扩张的 本原元（primitive element）。

例子

这些例子都是向 $\mathbf{Q}$ 中添加 $\mathbf{C}$ 中的元素得到的。

1. 对于无平方因子的整数 $D\ne 0,1$，二次域 $\mathbf{Q}(\sqrt{D})$ 就是在域 $\mathbf{Q}$ 中添加了 $\sqrt{D}\in \mathbf{C}\setminus \mathbf{Q}$ 得到的单扩张。它的扩张次数是 $2$，因为 $\{1,\sqrt{D}\}$ 构成了一组基。
2. 域 $\mathbf{Q}(\sqrt{2},\sqrt{3})$ 就是在域 $\mathbf{Q}$ 中添加了 $\sqrt{2}$ 和 $\sqrt{3}$ 得到的扩张。当然有 $\mathbf{Q}(\sqrt{2},\sqrt{3})=\mathbf{Q}(\sqrt{2})(\sqrt{3})=\mathbf{Q}(\sqrt{3})(\sqrt{2})$，即最后的扩张与元素的添加顺序和方式无关。这也是单扩张，因为 $\mathbf{Q}(\sqrt{2},\sqrt{3})=\mathbf{Q}(\sqrt{2}+\sqrt{3})$。它的扩张次数是 $4$，因为 $\{1,\sqrt{2},\sqrt{3},\sqrt{6}\}$ 构成了一组基。
3. 域 $\mathbf{Q}(\pi )$ 也是单扩张，其中，$\pi$ 是圆周率。它是无限扩张，因为 $\mathbf{Q}[\pi ]\subseteq \mathbf{Q}(\pi )$ 已经有一组基 $\{1,\pi ,{\pi }^2,\cdots \}$。
4. 域 $\mathbf{Q}(\pi ,\mathrm{e})$ 是有限生成的扩张，但不是单扩张。其中，$\pi$ 是圆周率，$\mathrm{e}$ 是自然对数的底。

这些例子说明，单扩张的性质可能相差悬殊。这取决于添加的元素的性质。

代数扩张

为了分析向域中添加元素可能出现的所有情形，不妨仿照前文对域的特征的讨论，考察多项式环 $F[x]$ 到扩张 $E/F$ 的环同态。此处的 $F[x]$ 起到了前文的整数环 $\mathbf{Z}$ 的作用：它正是在域 $F$ 中添加不定元 $x$ 后且对加、减、乘封闭的结构的「原型」³。

设环同态 $\phi :F[x]\to E$ 满足 $\phi$ 限制在 $F$ 上是恒等映射，且 $\phi (x)=\alpha$，即将不定元映射到扩张 $E$ 中的某个元素。此时，因为像 $\phi (F[x])=F[\alpha ]$ 必然是整环，同态的核 $\ker \phi$ 必然是多项式环 $F[x]$ 的素理想。域上的多项式环是主理想整环，因而它必然有 $(f(x))$ 的形式，其中 $f(x)=0$ 或 $f(x)$ 是 $F[x]$ 中的不可约元。对此有如下讨论：

1. 当同态的核 $\ker \phi =\{0\}$ 时，多项式环 $F[x]$ 嵌入到 $E$ 中，它的像 $F[\alpha ]$ 是整环。因而，域 $E$ 中同时包含 $F$ 和 $\alpha$ 的最小的域就是 $F[\alpha ]$ 的分式域，即 $F(\alpha )$。这个记号，既可以解释为将有理分式域 $F(x)$ 中的不定元代入 $\alpha$ 的结果，也可以解释为域 $F$ 上由 $\alpha$ 生成的单扩张：这两个解释在这个语境下得到的结果是一致的；

2. 当同态的核 $\ker \phi =(f(x))$，且 $f(x)$ 为不可约元时，就成立 $\phi (f(x))=f(\alpha )=0$，即 $\alpha \in E$ 是 $F$ 上的多项式 $f(x)$ 的根。因为 $F$ 是域，不妨设 $f(x)$ 是首一多项式。此时同态 $\phi$ 的像是域 $F(\alpha )$，故而有

   $$F[x]/(f(x))\cong F(\alpha ).$$

   此时又可以分为两种情形：

   1. 如果 $f(x)$ 是一次多项式，即 $f(x)=x-\alpha$ 时，有 $\alpha \in F$，故而扩张 $F(\alpha )=F$ 是平凡的；
   2. 其余情形，$f(x)$ 是高于一次的不可约多项式，且 $\alpha \in E\setminus F$，此时的像 $F[\alpha ]$ 已经是包含 $F$ 和 $\alpha$ 的域，因而，它就是 $F(\alpha )$，即 $F$ 上由 $\alpha$ 生成的扩张，且 $F(\alpha )\supset F$ 不是平凡的。

这些讨论启发了如下的定义：

代数元与超越元

对于扩张 $E/F$，如果元素 $\alpha \in E$ 是 $F$ 上某个非零多项式 $f(x)$ 的根，则称 $\alpha$ 是 $F$ 上的 代数元（algebraic element）；否则，称元素 $\alpha$ 是 $F$ 上的 超越元（transcendental element）。

极小多项式

对于域 $F$ 上的代数元 $\alpha$，以 $\alpha$ 为根且次数最小的首一多项式 $f(x)$ 称作它的 极小多项式（minimal polynomial）。

此处的极小多项式就是前文分析中的不可约多项式 $f(x)$。当然，也可以直接证明极小多项式都是不可约的。极小多项式 $f(x)$ 的极小性就意味着，只要域 $F$ 上的多项式以 $\alpha$ 为根，就必然能够分解出因子 $f(x)$。

例子

1. $\sqrt{2}$ 是 $\mathbf{Q}$ 上的代数元，极小多项式是 $x^2-2$。
2. $\sqrt{2}$ 是 $\mathbf{R}$ 上的代数元，极小多项式是 $x-\sqrt{2}$。
3. $\pi$ 是 $\mathbf{Q}$ 上的超越元。
4. 一般地，$\mathbf{Q}$ 上的代数元称为 代数数（algebraic number），而超越元称为 超越数（transcendental number）。特别地，如果代数数的极小多项式是首一多项式，它就称作 代数整数（algebraic integer）。代数扩张中的全体代数整数构成环。例如，二次域 $\mathbf{Q}(\sqrt{D})$ 中的代数整数就构成二次整数环 $\mathbf{Z}[\omega ]$。此处记号的含义见 二次整数环 页面。

代数扩张与超越扩张

对于扩张 $E/F$，如果域 $E$ 的元素都是 $F$ 中的代数元，则称域 $E$ 是 $F$ 上的 代数扩张（algebraic extension）；否则，称域 $E$ 是 $F$ 上的 超越扩张（transcendental extension）。

单扩张的结果，根据添加元素的性质不同，可以分为两类。当添加的元素是超越元时，单扩张总是同构于有理分式域。此时，没有任何可以进一步化简的可能性。但是，当添加的元素是代数元时，单扩张实际上就是 $F[\alpha ]$，即将 $\alpha$ 直接替换多项式环 $F[x]$ 中的不定元 $x$ 得到的结果。从初等的视角看，相较于超越元的情形，此时扩域中的元素可以没有分母；这意味着，类似于初等算术中「分母有理化」的过程，在代数元的单扩张中总是可行的。因为算法竞赛中涉及到的扩域主要是单代数扩张，下一节要对它的计算做更为细致的讨论。

单代数扩张的重要性，也反映在如下的定理中：

定理

域扩张是有限扩张，当且仅当它是有限生成的代数扩张。

证明

设 $F$ 为域，$E=F({\alpha }_1,\cdots ,{\alpha }_n)$ 为域上的有限生成代数扩张，即 ${\alpha }_i$ 都是 $F$ 上的代数元。设 $E_i=F({\alpha }_1,\cdots ,{\alpha }_i)$，则 $E_0=F$ 且 $E_n=E$。注意到，${\alpha }_i$ 必然是 $E_{i-1}$ 上的代数元，因为 ${\alpha }_i$ 在域 $F$ 上的极小多项式也是 $E_{i-1}$ 上的多项式；而且 ${\alpha }_i$ 在 $E_{i-1}$ 上的极小多项式次数必然不超过 ${\alpha }_i$ 在域 $F$ 上的极小多项式次数。故而，$[E_i:E_{i-1}]$ 必然是有限的，根据域扩张次数的乘法原理，$[E:F]={\prod }_{i=1}^n[E_i:E_{i-1}]$ 也是有限的。反过来，从 $E_0=F$ 开始，对于已经构造好的 $E_i$，可以每次都在 $E\setminus E_i$ 中选择元素 ${\alpha }_{i+1}$ 加入到 $E_i$ 中，得到扩域 $E_{i+1}=E_i({\alpha }_{i+1})$，直到 $E_n=E$ 为止。因为扩张的次数在不断的降低，这个过程必然在有限步内终止。因此，有限扩张必然是有限生成的代数扩张。

这意味着，要理解有限扩张的性质，只要理解单代数扩张即可。因为有限扩张总是可以通过有限多个的单代数扩张得到。

单代数扩张的结构与计算

本节中，设 $F$ 是数域，$E$ 是它的扩域，且 $\alpha \in E\setminus F$ 是域 $F$ 上的代数元。设 $\alpha$ 的极小多项式是 $f(x)$，且多项式 $f(x)$ 是 $n$ 次首一多项式，亦即

$$f(x)=x^n+a_{n-1}{x}^{n-1}+\cdots +a_{1}x+a_0,$$

其中，$a_0,a_1,\cdots ,a_{n-1}\in F$ 且 $f(x)$ 在 $F$ 上不可约。

同构关系 $F(\alpha )\cong F[x]/(f(x))$ 指出，扩域 $F(\alpha )$ 中的运算就是模 $f(x)$ 的多项式的计算。根据多项式的带余除法，只需要考虑所有次数小于 $n=\mathrm{deg}f(x)$ 的多项式的同余类就可以了。对于这些多项式，自然的一组基就是 $\{1,\alpha ,\cdots ,{\alpha }^{n-1}\}$。因此，有如下结论：

定理

在本节的假设下，扩域 $F(\alpha )$ 可以写作

$$F(\alpha )=\{\lambda (\alpha )={\lambda }_0+{\lambda }_1\alpha +\cdots +{\lambda }_{n-1}{\alpha }^{n-1}:{\lambda }_0,{\lambda }_1,\cdots ,{\lambda }_{n-1}\in F\}.$$

其中，$\lambda (x)$ 遍历全体次数小于 $n$ 的多项式。因此，扩张次数 $[F(\alpha ):F]=n$，即 $\alpha$ 的极小多项式的次数。扩域中，元素 $\lambda (\alpha )$ 和 $\mu (\alpha )$ 的加法，就是多项式的加法，即对应位置的系数相加；元素 $\lambda (\alpha )$ 和 $\mu (\alpha )$ 的乘法，结果可以写作 $\rho (\alpha )$，其中 $\rho (x)$ 是乘积 $\lambda (x)\mu (x)$ 除以 $f(x)$ 的余式。

当然，作为域，还可以计算 $F(\alpha )$ 中元素的除法。根据定理中描述的乘法的过程，这相当于求解多项式环上的 线性同余方程。类比整数的做法，要计算商 $\lambda (\alpha )/\mu (\alpha )$，可以先确定 $\mu (\alpha )$ 的乘法逆元，再乘以 $\lambda (\alpha )$ 即可。要计算 $\mu (\alpha )$ 的乘法逆元，只要解同余方程 $\mu (x)\xi (x)\equiv 1(\mathrm{mod}f(x))$ 即可。这可以通过扩展欧几里得算法实现。

下面，通过几个具体的例子理解计算的细节。

例子

考察扩域 $\mathbf{Q}(\alpha )$，其中的 $\alpha$ 是方程 $x^3-2x-2=0$ 的一个根。要计算

$$\frac{1+\alpha }{1+\alpha +{\alpha }^2}$$

的值。

第一步是计算 $1+\alpha +{\alpha }^2$ 的逆元，也就是要计算同余方程

$$(x^2+x+1)\xi (x)+(x^3-2x-2)\nu (x)=1$$

的解。对此应用扩展欧几里得算法。先做辗转相除法，即有如下过程：

$$\begin{array}{rl}{x}^3-2x-2& =(x-1)(x^2+x+1)+(-2x-1),\\ x^2+x+1& =\left(-\frac{1}{2}x-\frac{1}{4}\right)(-2x-1)+\frac{3}{4},\\ -2x-1& =\left(-\frac{8}{3}x-\frac{4}{3}\right)\frac{3}{4}.\end{array}$$

再计算同余方程中的系数，即有

$$\begin{array}{rl}\frac{3}{4}& =(x^2+x+1)+\left(\frac{1}{2}x+\frac{1}{4}\right)(-2x-1)\\ & =(x^2+x+1)+\left(\frac{1}{2}x+\frac{1}{4}\right)\left((x^3-2x-2)-(x-1)(x^2+x+1)\right)\\ & =\left(-\frac{1}{2}{x}^2+\frac{1}{4}x+\frac{5}{4}\right)(x^2+x+1)+\left(\frac{1}{2}x+\frac{1}{4}\right)(x^3-2x-2).\end{array}$$

因而，方程的解为

$$\xi (x)=-\frac{2}{3}{x}^2+\frac{1}{3}x+\frac{5}{3},\nu (x)=\frac{2}{3}x+\frac{1}{3}.$$

这说明 $1+\alpha +{\alpha }^2$ 的逆元是

$$-\frac{2}{3}{\alpha }^2+\frac{1}{3}\alpha +\frac{5}{3}.$$

第二步，就是计算逆元和 $1+\alpha$ 的乘积。对此，有

$$\begin{array}{rl}(1+\alpha )\left(-\frac{2}{3}{\alpha }^2+\frac{1}{3}\alpha +\frac{5}{3}\right)& =-\frac{2}{3}{\alpha }^3-\frac{1}{3}{\alpha }^2+2\alpha +\frac{5}{3}\\ & =-\frac{2}{3}(2\alpha +2)-\frac{1}{3}{\alpha }^2+2\alpha +\frac{5}{3}\\ & =-\frac{1}{3}{\alpha }^2+\frac{2}{3}\alpha +\frac{1}{3}.\end{array}$$

这就是最后的答案。

在例子中只用到了 $\alpha$ 是方程的一个根这个条件，却并没有指定它是任何一个具体的根。多项式 $x^3-2x-2=0$ 在复数域 $\mathbf{C}$ 有一个实根和一对共轭复根，将它们中的任何一个添加进有理数域 $\mathbf{Q}$ 中得到的扩域都是同构的。也就是说，这三个互异的根在代数的视角上是没有区别的。

一般地，对于域 $F$ 上的不可约多项式 $f(x)$，在扩域中有不同的根 $\alpha \ne \beta$，这些根在分别对域 $F$ 做单扩张时表现出相同的代数性质，这些根互相称为 共轭（conjugate）。复数域上的通常意义的共轭，就是这一概念在域扩张 $\mathbf{C}/\mathbf{R}$ 上的特例。

例子

考察扩域 ${\mathbf{F}}_2(\alpha )$，其中的 $\alpha$ 是方程 $x^2+x+1=0$ 的一个根。一般地，对于 $a+b\alpha$ 和 $c+d\alpha$，有运算规则

$$\begin{array}{rl}(a+b\alpha )+(c+d\alpha )& =(a+c)+(b+d)\alpha ,\\ (a+b\alpha )(c+d\alpha )& =ac+(ad+bc)\alpha +bd{\alpha }^2\\ & =(ac+bd)+(ad+bc+bd)\alpha .\end{array}$$

这提供了类似于复数域上的运算法则。大多数读者对于这样的根 $\alpha$ 都应当是陌生的，但这并不妨碍对这样的域中的元素进行运算。实际上，有 $[{\mathbf{F}}_2(\alpha ):{\mathbf{F}}_2]=2$，因而，作为线性空间 $|{\mathbf{F}}_2(\alpha )|=4$，即这样得到的是大小为 $4$ 的有限域。稍后会看到，所有的有限域都是这样构造的。

在小规模运算时，对首一多项式取模 $f(x)$ 的运算通常可以通过代入

$$x^n=-a_{n-1}{x}^{n-1}-\cdots -a_{1}x-a_0$$

对目标多项式降次来进行。而且，对于低次的扩张，往往可以直接计算出系数的运算规则，使用类似复数类的实现而不必每次都计算取模等过程。

作为单代数扩张的实例，可以参考下文中的有限域的 参考实现。

此处描述的算法在实践中都只能处理扩张次数比较低的情形，这对于绝大多数算法竞赛中的应用都是足够的。对于扩张次数高到成为复杂度瓶颈的情形，应当采取适当的多项式技术（快速傅里叶变换、快速数论变换、多项式快速取余、多项式欧几里得 等）加速运算。

分裂域

上文已经对单代数扩张的结构做了详尽的讨论。但是，这样的扩张往往并不充分：

例子

考察扩张 $\mathbf{Q}(\sqrt[3]{2})/\mathbf{Q}$。代数元 $\sqrt[3]{2}$ 在域 $\mathbf{Q}$ 上的极小多项式是 $x^3-2$。在复数域 $\mathbf{C}$ 中，多项式 $x^3-2$ 有三个根，即 $\sqrt[3]{2},\sqrt[3]{2}\omega ,\sqrt[3]{2}{\omega }^2$，其中，$\omega ={\mathrm{e}}^{2\pi \mathrm{i}/3}$ 是 $1$ 的三次原根。尽管 $\mathbf{Q}(\sqrt[3]{2})\cong \mathbf{Q}(\sqrt[3]{2}\omega )\cong \mathbf{Q}(\sqrt[3]{2}{\omega }^2)$，但是 $\mathbf{Q}(\sqrt[3]{2})$ 中并没有另外的两个根，这使得 $\sqrt[3]{2}+\sqrt[3]{2}\omega$ 这种运算就已经无法进行。如果要完整地考察这三个根，需要对域 $\mathbf{Q}(\sqrt[3]{2})$ 做进一步扩张，即扩张至 $\mathbf{Q}(\sqrt[3]{2},\sqrt[3]{2}\omega ,\sqrt[3]{2}{\omega }^2)$。

前文已经说明，要做这样的扩张，只要对元素逐个做单扩张即可。应当注意的是，$\sqrt[3]{2}\omega$ 在域 $\mathbf{Q}$ 中和在域 $\mathbf{Q}(\sqrt[3]{2})$ 中的极小多项式并不相同：前者是 $x^3-2\in \mathbf{Q}[x]$，后者则是 $x^2+\sqrt[3]{2}x+\sqrt[3]{4}\in \mathbf{Q}(\sqrt[3]{2})[x]$，因为有

$$x^3-2=(x-\sqrt[3]{2})(x^2+\sqrt[3]{2}x+\sqrt[3]{4}).$$

原来的极小多项式在域的扩张后分解出一次因子，因而剩余的根的极小多项式的次数低于原来的域上的极小多项式。域不断扩张的过程，就是多项式不断「分裂」的过程。因此，每次单扩张时，都需要重新确定极小多项式。

将多项式的全部根都添加到域中，得到的就是多项式的分裂域。

分裂

设 $F$ 为域。如果多项式 $f(x)$ 在 $F[x]$ 中可以分解为一系列一次因子的乘积，就称多项式 $f(x)$ 在域 $F$ 中 分裂（split）。

分裂域

对于域 $F$ 上的多项式 $f(x)$，如果扩张 $E/F$ 满足 $f(x)$ 在域 $E$ 中分裂但不在任何 $E$ 的真子域中分裂，就称域 $E$ 是多项式 $f(x)$ 的 分裂域（splitting field）。

可以证明，如同单扩张一样，给定多项式的分裂域在同构意义下是唯一确定的，与具体的构造方法无关。分裂域总是有限扩张。

正规扩张

对于代数扩张 $E/F$，如果对所有 $\alpha \in E$ 都有 $\alpha$ 的极小多项式在 $E$ 中分裂，则称域 $E$ 是域 $F$ 的 正规扩张（normal extension）。

正规扩张在 Galois 理论中起到基础的作用。

代数闭域

前文提及的多数扩张的概念原则上需要在比扩张更大的域内进行。尽管对于单扩张的情形，通过多项式环可以不依赖于更大的域构造出域的扩张，但是对于一般的情形并没有这样的手段。对于有理数域 $\mathbf{Q}$ 和实数域 $\mathbf{R}$，总是可以假定代数扩张包含在复数域 $\mathbf{C}$ 内部。对于有限域，并没有类似的已知的域。其实，对于所有的域，都存在代数闭包，使得域上所有的代数扩张都可以假定在代数闭包内进行。这就彻底解决了这一问题。

代数闭包

对于域 $F$，如果域 $\overline{F}$ 是域 $F$ 的代数扩张，且所有的 $f(x)\in F[x]$ 都在 $\overline{F}$ 中分裂，则称域 $\overline{F}$ 是域 $F$ 的 代数闭包（algebraic closure）。

代数闭包是域上的正规扩张。它的构造方式也基本上就是将所有可能的多项式的根添加到域中。而且和分裂域一样，某个域的代数闭包在同构意义下也是唯一的。

定理

任何域 $F$ 都有代数闭包。

证明

证明的困难来自于集合论。此处引用 Artin 的一个证明。

证明的第一部分从 $F$ 出发，构造了扩张 $K_1/F$ 使得所有 $F$ 上的多项式在 $K_1$ 中都有至少一个根。对于域 $F$，考察多元多项式环 ⁴ $R=F[\cdots ,x_f,\cdots ]$，其中的不定元 $x_f$ 的下标取遍所有 $F$ 上的首一多项式。此时，由所有 $f(x_f)$ 生成的理想记作 $I$。首先，$I\ne R$，故而极大理想 $M\supseteq I$ 存在。否则，如果 $1\in I$，必然存在有限多个域 $F$ 上的首一多项式 $f_i$ 和相应的环 $R$ 中的元素 $g_i$ 使得 $g_1{f}_1(x_{f_1})+\cdots +g_k{f}_k(x_{f_k})=1$ 成立。设 $F({\alpha }_1,\cdots ,{\alpha }_k)$ 为向 $F$ 中添加 $f_i(x)$ 的根 ${\alpha }_i$ 后得到的代数扩张，则在 $F({\alpha }_1,\cdots ,{\alpha }_k)$ 中令上面得到的恒等式中 $x_{f_i}$ 都代入 ${\alpha }_i$，而在各个 $g_i$ 中出现的其它不定元 $x_f$ 都带入 $0$，则得到 $F({\alpha }_1,\cdots ,{\alpha }_k)$ 上的等式 $0=1$，这矛盾。故而，$I\ne R$，极大理想 $M$ 的构造是合法的。此时商环 $R/M$ 是域，记作 $K_1$，且任何 $F$ 上的首一多项式 $f(x)$ 都在 $K_1$ 中有根 $\overline{x_f}$。

证明的第二部分则归纳地得到了包含 $F$ 的一个代数闭域 $K$（定义见下文）。重复上述构造，基于域 $K_i$ 可以构造出域 $K_{i+1}$，使得 $K_i$ 的多项式在 $K_{i+1}$ 中都至少有一个根。而且，$K_i$ 自然地嵌入到 $K_{i+1}$ 中，所以可以定义它们的并集 $K={\bigcup }_{i=1}^{\infty }{K}_i$。容易验证，这也是域，而且 $K$ 上的任何多项式的系数必然全部包含在某个 $K_i$ 中，故而它的一个根必然出现 $K_{i+1}\subseteq K$ 中。这说明 $K$ 上的所有多项式都在 $K$ 上至少有一个根，所以，$K$ 是代数闭域。

最后，令 $K$ 中所有 $F$ 上的代数元组成的集合记作 $\overline{F}$。它显然是域；因为对于任何 $\alpha ,\beta \in \overline{F}$，都有 $\alpha \pm \beta ,\alpha \beta ,\alpha /\beta \in F(\alpha ,\beta )\subseteq \overline{F}$。它也是 $F$ 的代数扩张，因为它的元素都是 $F$ 上的代数元。对于 $F$ 上的多项式 $f(x)$，它的所有根都是 $F$ 上的代数元，故而也在 $\overline{F}$ 中，故而必然可以分裂为一次因子的乘积。这就说明 $\overline{F}$ 是 $F$ 上的代数闭包。

例子

1. 实数域 $\mathbf{R}$ 的代数闭包是复数域 $\mathbf{C}$。
2. 有理数域 $\mathbf{Q}$ 的代数闭包是全体代数数（即域扩张 $\mathbf{C}/\mathbf{Q}$ 中的代数元）的集合，记作 $\overline{\mathbf{Q}}$。

所有的代数闭包的代数扩张都是平凡的。这样的域称为代数闭域。

代数闭域

如果域 $F$ 上任意非常数多项式 $f(x)$ 都至少有一个根 $\alpha \in F$，那么就称域 $F$ 为一个 代数闭域（algebraically closed field）。

事实上，它有如下等价定义：

定理

对于域 $F$，以下性质都是等价的：

1. 域 $F$ 是代数闭域；
2. 域 $F$ 上的所有多项式 $f(x)$ 都分裂；
3. 域 $F$ 上的不可约多项式只有一次多项式；
4. 域 $F$ 没有非平凡的代数扩张；
5. 域 $F$ 没有非平凡的有限扩张；
6. 域 $F$ 是某个域的代数闭包。

证明

前五条性质的等价性显然，考察定义即可。对于第六条，代数闭域显然是自身的代数闭包，因为它没有非平凡的代数扩张；反过来，要证明域 $F$ 的代数闭包必然是代数闭域。设 $\overline{F}$ 是域 $F$ 的代数闭包，且 $f(x)$ 是 $\overline{F}$ 上的多项式。设 $\alpha$ 是 $f(x)$ 的分裂域中 $f(x)$ 的一个根，且 $f(x)$ 的非零系数的集合是 $S\subseteq \overline{F}$。那么，因为 $F(S)(\alpha )=F(S\cup \{\alpha \})$ 是有限扩张，$\alpha$ 必然也是 $F$ 上的代数元，故而根据代数闭包的定义，$\alpha$ 在 $F$ 上的极小多项式在域 $\overline{F}$ 中分裂，故而 $\alpha \in \overline{F}$。这说明，$\overline{F}$ 上任意多项式都有至少一个根。

最后，代数基本定理 ⁵ 说明，$\mathbf{C}$ 是代数闭域。实数域 $\mathbf{R}$ 上的不可约多项式至多是二次的，或者等价地，它上面的代数扩张至多是二次扩张，就是因为通过代数扩张能够得到的最大的域就是 $\mathbf{C}$。

可分扩张

分裂域的概念保证了对于任何域上的多项式，总有扩域能够包括它的所有根，且分裂域精确地给出了这样的最小的扩域。多项式的性质和它的分裂域的性质紧密联系。但是，如果希望通过多项式的分裂域来研究多项式的性质，那么首先要面临的一个问题就是，多项式的分裂域与多项式的根的重数无关。因而，如果有可能，应当考虑多项式的某种意义上的「最简表示」。受此启发，把在域的代数闭包中也没有重根的多项式称为可分多项式。

可分多项式

对于域 $F$ 上的多项式 $f(x)$，如果 $f(x)$ 在 $F$ 的代数闭包 $\overline{F}$ 中没有重根，即它分解成一次因子的乘积时没有重复因子，那么 $f(x)$ 称为 可分的（separable）。

因为总是要扩张到域 $F$ 的代数闭包上讨论，可分多项式的判断其实与域 $F$ 的选取无关。但是，因为多项式的系数在 $F$ 中，应当考虑给出一个判断方法，能够使得在域 $F$ 上就能判断多项式是否可分而不必显式地构造出其扩域。

熟悉分析学的读者知道，多项式函数的重根有无可以通过它的导数判断：多项式函数的重根同样是它的导数的根。虽然多项式和多项式函数并非一致的概念，但是判断多项式函数重根有无的方法可以类比地迁移到多项式上。多项式的导数可以形式地定义如下：

形式导数

域 $F$ 上的多项式

$$f(x)=a_0+a_{1}x+a_2{x}^2+\cdots +a_{n-1}{x}^{n-1}+a_n{x}^n=\sum _{i=0}^n{a}_i{x}^i$$

的 （形式）导数（derivative），记作 $Df(x)$，定义为多项式

$$Df(x)=a_1+2a_{2}x+\cdots +(n-1)a_{n-1}{x}^{n-1}+n{a}_n{x}^{n-1}=\sum _{i=1}^{n}i{a}_i{x}^{i-1}.$$

这个定义对于所有域上的多项式都适用，不依赖于任何拓扑结构，此处的导数算子 $D$ 只是把一个多项式映射到了另一个多项式。而且，可以通过对比系数验证，常见的导数运算法则，比如 $D(f(x)g(x))=(Df(x))g(x)+f(x)(Dg(x))$ 等，对于形式导数依然成立。

进而，要检查多项式 $f(x)$ 和它的导数 $Df(x)$ 在分裂域中是否有相同的根，可以不显式地构造出这个分裂域，而是通过它们的最小公因子来判断；这是因为多项式的根总是出现在它的极小多项式中，重复的根意味着相应的极小多项式因子也重复。于是，有重根的判断法则如下：

定理

对于域 $F$ 上的多项式 $f(x)$，如果 $f(x)$ 有重根 $\alpha$，那么导数 $Df(x)$ 也有同样的根 $\alpha$。进而，多项式 $f(x)$ 可分的充分必要条件是 $f(x)$ 与它的导数 $Df(x)$ 互素，即 $\gcd (f(x),Df(x))=1$。

证明

首先，因为带余除法在扩域中依然保持，欧几里得算法的结果也和扩域的选取无关，所以只要在分裂域中讨论它们的公因子就好了。由此，设 $\alpha$ 是 $f(x)$ 的 $k>1$ 重根，则分裂域中有分解 $f(x)=(x-\alpha {)}^{k}g(x)$，于是它的导数 $Df(x)=k(x-\alpha {)}^{k-1}g(x)+(x-\alpha {)}^{k}Dg(x)$ 必然也有根 $\alpha$。反过来，如果 $f(x)$ 和 $Df(x)$ 都有根 $\alpha$，那么对于分裂域中的分解 $f(x)=(x-\alpha )g(x)$，就有 $Df(x)=(x-\alpha )Dg(x)+g(x)$，故而 $\alpha$ 也是 $g(x)$ 的根，因而 $\alpha$ 是 $f(x)$ 的重根。这就说明定理的第一部分。进而，多项式 $f(x)$ 有重根 $\alpha$，等价于 $x-\alpha$ 是 $\gcd (f(x),Df(x))$ 的因子。所以，多项式 $f(x)$ 不可分，就等价于 $\gcd (f(x),Df(x))$ 次数大于等于一。

域上的多项式总是可以分解为若干个不可约多项式的乘积。因为（相伴意义下）不同的不可约多项式总是有着不同的根，根的重复自然联系到相应的多项式因子的重复。那么，如果多项式的分解中没有重复的不可约因子，是否就能判断多项式可分呢？换句话说，不可约的多项式是否都可分？很遗憾，在一般的情形下，无法得到肯定的答案。问题出现在有限特征的域。

对于域 $F$ 上的不可约多项式 $f(x)$，多项式 $\gcd (f(x),Df(x))$ 作为 $f(x)$ 的因子，只能有两种情形，即 $1$ 或者 $f(x)$。对于前一种情况，多项式 $f(x)$ 自然是可分的；问题出现在后一种情况。但是，由于导数的定义中已经保证 $Df(x)=0$ 或者 $\mathrm{deg}Df(x)<\mathrm{deg}f(x)$，多项式 $f(x)$ 成为 $Df(x)$ 的因子，只能说明 $Df(x)=0$。这在有限特征的域中是有可能的。

对于特征为 $p$ 的域 $F$，如果 $Df(x)=0$，则多项式的所有非零系数都只能出现在次数恰为 $p$ 的倍数的项上，即多项式 $f(x)$ 可以写作

$$f(x)=a_0+a_p{x}^p+a_{2p}{x}^{2p}+\cdots +a_{(k-1)p}{x}^{(k-1)p}+a_{kp}{x}^{kp}.$$

如果真的存在域 $F$ 上的多项式 $f(x)$ 既不可约也不可分，则它只能有这种形式。但是，如果域 $F$ 中的所有元素总有 $p$ 次根，即对每个系数 $a_{jp}$ 都存在 $b_j\in F$ 使得 $a_{jp}$ 可以写作 $b_j^p$ 的形式，那么，根据 Frobenius 自同态，总有

$$\begin{array}{rl}f(x)& =a_0+a_p{x}^p+a_{2p}{x}^{2p}+\cdots +a_{(k-1)p}{x}^{(k-1)p}+a_{kp}{x}^{kp}\\ & =b_0^p+b_1^p{x}^p+b_2^p{x}^{2p}+\cdots +b_{k-1}^p{x}^{(k-1)p}+b_k^p{x}^{kp}\\ & ={\left(b_0+b_{1}x+b_{2}x+\cdots +b_{k-1}{x}^{k-1}+b_k{x}^k\right)}^p.\end{array}$$

因而，这样的域 $F$ 上并不存在这种形式的不可约多项式。因而，这种域上，所有不可约多项式都是可分的。这种域称为完美域。

完美域

如果域 $F$ 上的所有不可约多项式都是可分多项式，就称它为 完美域（perfect field）。

对于完美域，可分多项式的概念和唯一分解中没有平方因子的多项式的概念是等同的。

定理

设域 $F$ 是完美域，则 $F$ 上的多项式可分，当且仅当它可以写作若干个（相伴意义下）不同的不可约多项式的乘积。

本节的讨论其实已经足够给出移除多项式中的重复因子的方法，它是对多项式的因式分解算法中的关键步骤。但这超出了本文范畴，有兴趣的读者可以参考文末的相关资料。

这些讨论其实也给出了完美域的刻画：

定理

域 $F$ 为完美域，当且仅当域 $F$ 的特征是零，或者域 $F$ 的特征是 $p$ 且任何元素 $x\in F$ 都有 $p$ 次根（即 Frobenius 自同态也是自同构）。

有理数域 $\mathbf{Q}$ 和下文会讨论的有限域 ${\mathbf{F}}_q$ 都是完美域。

对于域不是完美域的情形，的确存在不可分的不可约多项式。

例子

考虑 ${\mathbf{F}}_2$ 的有理分式域 ${\mathbf{F}}_2(t)$ 上的多项式 $x^2-t$。因为 ${\mathbf{F}}_2(t)$ 是唯一分解整环 ${\mathbf{F}}_2[t]$ 的分式域，且 $t$ 是 ${\mathbf{F}}_2[t]$ 中的素元，则对素元 $t$ 应用 Eisenstein 判别法可知 $x^2-t$ 在 ${\mathbf{F}}_2[t]$ 中不可约，故而在 ${\mathbf{F}}_2(t)$ 中也不可约。但是，它的导数为 $0$，因而 $x^2-t$ 并不可分。事实上，在扩域 ${\mathbf{F}}_2(t)(\sqrt{t})$ 中，它有二重根 $\sqrt{t}$。

最后回到域的扩张的讨论。

可分扩张

对于代数扩张 $E/F$，如果对所有 $\alpha \in E$ 都有 $\alpha$ 的极小多项式是可分多项式，那么称域 $E$ 是域 $F$ 的 可分扩张（seperable extension）。

完美域上的代数扩张都是可分扩张。这也可以作为完美域的等价定义。

如果一个代数扩张既是正规扩张，也是可分扩张，它也称作 Galois 扩张。Galois 扩张中，任何不可约多项式都没有重根，且根的数目都恰好等于多项式的次数，因而对根的置换可以充分地反映域扩张和多项式的性质。这样的扩张提供了建立 Galois 理论的基石。有兴趣的读者可以参考文末的相关资料。

分圆域

作为域扩张的简单例子，本节讨论分圆域。另一个域扩张的简单例子是 二次域。

单位根群

复数域 $\mathbf{C}$ 中，多项式 $x^n=1$ 的根称为 $n$ 次单位根（$n$-th root of unity）。记 ${\zeta }_n={\mathrm{e}}^{2\pi \mathrm{i}/n}$。那么，全体 $n$ 次单位根就是集合 $C_n=\{{\zeta }_n^k:k\in \mathbf{Z}\}$。在乘法运算下，$C_n$ 构成 $n$ 次循环群，可以记作 $⟨{\zeta }_n⟩$，称为 $n$ 次单位根群。群 $C_n$ 的生成元，也就是那些阶恰好为 $n$ 的元素，称为 $n$ 次本原单位根（primitive $n$-th root of unity）。$n$ 次本原单位根的集合 $P_n=\{{\zeta }_n^k:k\in \mathbf{Z},k\perp n\}$，恰有 $\phi (n)$ 个元素；其中，$\phi (n)$ 是 欧拉函数。将单位根群 $C_n$ 的元素按照它的阶分类，就得到如下分解：

$$C_n=\bigcup _{d|n}{P}_d.$$

对两边元素计数，就得到恒等式 $n={\sum }_{d\mid n}\phi (d)$。

分圆域

分圆域是将单位根添加到有理数域中得到的扩域。

分圆域

将 $n$ 次复单位根 ${\zeta }_n={\mathrm{e}}^{2\pi \mathrm{i}/n}$ 添加到有理数域 $\mathbf{Q}$ 中得到的扩域 $\mathbf{Q}({\zeta }_n)$ 称为 $n$ 次分圆域（$n$-th cyclotomic field）。

因为全体 $n$ 次单位根在乘法运算下构成循环群 $⟨{\zeta }_n⟩$，分圆域 $\mathbf{Q}({\zeta }_n)$ 也包括所有这些 $n$ 次单位根。其实，$\mathbf{Q}({\zeta }_n)$ 正是域 $\mathbf{Q}$ 上多项式 $x^n-1$ 的分裂域。

定理

分圆域 $\mathbf{Q}({\zeta }_n)$ 是有理数域 $\mathbf{Q}$ 上多项式 $x^n-1$ 的分裂域。

证明

设 $F$ 为有理数域 $\mathbf{Q}$ 上多项式 $x^n-1$ 的分裂域。因为 $\mathbf{Q}({\zeta }_n)$ 上有多项式 $x^n-1$ 的全体复根，所以 $F\subseteq \mathbf{Q}({\zeta }_n)$。反过来，因为 ${\zeta }_n\in F$，就必然有 $\mathbf{Q}({\zeta }_n)=F$。这就说明 $F=\mathbf{Q}({\zeta }_n)$。

这可以作为分圆域的等价定义。其实，将任何 $n$ 次本原单位根添加到分圆域中都能够得到 $\mathbf{Q}({\zeta }_n)$。

分圆多项式

分圆域 $\mathbf{Q}({\zeta }_n)$ 是有理数域 $\mathbf{Q}$ 上的单代数扩张。根据上文的分析，这样的域总是同构于某个多项式环的商环。为了得到这样的同构，需要分析 ${\zeta }_n$ 的极小多项式 $f(x)$。因为 ${\zeta }_n$ 是 $x^n-1$ 的根，所以 $f(x)$ 必然是 $x^n-1$ 的某个因子。这说明，需要考察多项式 $x^n-1$ 在 $\mathbf{Q}[x]$ 内的因式分解。根据 Gauss 引理，它必然可以在 $\mathbf{Z}[x]$ 中分解为若干个不可约的首一多项式的乘积。

因为 $\mathbf{Q}({\zeta }_n)$ 是分裂域，多项式 $x^n-1$ 有分解：

$$x^n-1=\prod _{\zeta \in C_n}(x-\zeta )=\prod _{d\mid n}\prod _{\zeta \in P_d}(x-\zeta ).$$

因为不同阶的单位根的代数性质不同，它们必然不会是同一个不可约多项式的根。因此，要考察 ${\zeta }_n$ 的极小多项式，只要考虑上述分解中的因子

$${\Phi }_n(x)=\prod _{\zeta \in P_n}(x-\zeta )$$

即可。单位根 ${\zeta }_n$ 的极小多项式，必然是 ${\Phi }_n(x)$ 的因子。而且，这样定义的 ${\Phi }_n(x)$ 有如下性质：

定理

${\Phi }_n(x)$ 是整系数首一多项式，且在 $\mathbf{Z}[x]$ 中不可约。

证明

由定义，${\Phi }_n(x)$ 显然是首一多项式。首先，要证明 ${\Phi }_n(x)\in \mathbf{Z}[x]$。根据 Gauss 引理，多项式 $x^n-1$ 在 $\mathbf{Z}[x]$ 和 $\mathbf{Q}[x]$ 中有着相同的分解，且每个因子都是整系数首一多项式。这个分解中，每个因子 $f(x)$ 都是 $\mathbf{Q}[x]$ 上不可约的，且在 $\mathbf{Q}({\zeta }_n)$ 中分裂；它的所有根都是 $n$ 次单位根，且必然有着相同的阶，所以这些根必然全部属于某一个 $P_d$ 而不能分别存在于不同的 $P_d$。这意味着，每个因子 $f(x)$ 都是某个 ${\Phi }_d(x)$ 的因子。故而，${\Phi }_n(x)$ 可以写成若干个的整系数首一多项式的乘积，必然也是整系数首一多项式。

接下来，要证明 ${\Phi }_n(x)$ 在 $\mathbf{Z}[x]$ 是不可约的。设它有分解 $f(x)g(x)$，且 $f(x)$ 在 $\mathbf{Z}[x]$ 中不可约，那么只要证明 $f(x)$ 包含所有 $n$ 次本原单位根即可。也就是说，设 $\zeta$ 是 $f(x)$ 的一个根，要证明对于所有 $k\perp n$，都有 ${\zeta }^k$ 也是 $f(x)$ 的根；由于 $k$ 总是可以分解为素数的乘积，所以只需要证明对于所有素数 $p\perp n$，${\zeta }^p$ 是 $f(x)$ 的根就可以了。假设不然，${\zeta }^p$ 是 $g(x)$ 的根。因而，$\zeta$ 是 $\mathbf{Z}[x]$ 中多项式 $f(x)$ 和 $g(x^p)$ 的共同的根。因为 $f(x)$ 是 $\zeta$ 在 $\mathbf{Q}$ 上的极小多项式，必然有 $f(x)$ 整除 $g(x^p)$；亦即存在 $h(x)\in \mathbf{Z}[x]$ 使得 $g(x^p)=f(x)h(x)$。等式两侧同时对 $p$ 取模，得到 ${\mathbf{F}}_p[x]$ 上的等式 $\overline{g}(x^p)=\overline{f}(x)\overline{h}(x)$。利用 Frobenius 自同态可知，$\overline{g}(x{)}^p=\overline{f}(x)\overline{h}(x)$。因为 ${\mathbf{F}}_p[x]$ 也是唯一分解整环，$\overline{g}(x)$ 和 $\overline{f}(x)$ 必然有不平凡的公因子，所以，$x^n-\overline{1}=\overline{f}(x)\overline{g}(x)$ 在 ${\mathbf{F}}_p$ 上不可分。但是，因为 $p\perp n$，它的形式导数 $n{x}^{n-1}$ 与它自身互素，这与它不可分矛盾。故而，可以证明 ${\zeta }^p$ 必然还是 $f(x)$ 的根，因而 $f(x)$ 包含所有 $n$ 次本原单位根，它就是 ${\Phi }_n(x)$。

这就说明，它就是 ${\zeta }_n$ 的极小多项式，也称为 $n$ 次分圆多项式（$n$-th cyclotomic polynomial）。上面的定义式指出，它有 $\phi (n)$ 个复根，且这些复根正是全体 $n$ 次本原单位根；其中，$\phi (n)$ 是 欧拉函数。这也说明，$\mathbf{Q}({\zeta }_n)/\mathbf{Q}$ 是 $\phi (n)$ 次扩张。

分圆域 $\mathbf{Q}({\zeta }_n)$ 中的代数整数环是 $\mathbf{Z}[{\zeta }_n]$。另外，当 $\phi (n)=2$ 时，分圆域是 二次扩张。具体来说，$\mathbf{Q}({\zeta }_4)$ 是二次域 $\mathbf{Q}(\sqrt{-1})$；$\mathbf{Q}({\zeta }_3)$ 和 $\mathbf{Q}({\zeta }_6)$ 相同，都是二次域 $\mathbf{Q}(\sqrt{-3})$。

利用分圆多项式，多项式 $x^n-1$ 在 $\mathbf{Z}[x]$ 中有唯一分解

$$x^n-1=\prod _{d\mid n}{\Phi }_d(x).$$

因此，$(x^d-1)\mid (x^n-1)$ 当且仅当 $d\mid n$。而且，对此式应用 Möbius 反演 可得

$${\Phi }_d(x)=\prod _{d\mid n}(x^d-1{)}^{\mu (n/d)}.$$

利用这个表达式，可以递归地计算出全部的分圆多项式。此处给出前几个分圆多项式的例子，便于读者熟悉。

分圆多项式

前 $10$ 个分圆多项式如下：

$$\begin{array}{rl}{\Phi }_1(x)& =x-1,\\ {\Phi }_2(x)& =x+1,\\ {\Phi }_3(x)& =x^2+x+1,\\ {\Phi }_4(x)& =x^2+1,\\ {\Phi }_5(x)& =x^4+x^3+x^2+x+1,\\ {\Phi }_6(x)& =x^2-x+1,\\ {\Phi }_7(x)& =x^6+x^5+x^4+x^3+x^2+x+1,\\ {\Phi }_8(x)& =x^4+1,\\ {\Phi }_9(x)& =x^6+x^3+1,\\ {\Phi }_{10}(x)& =x^4-x^3+x^2-x+1.\end{array}$$

一个有趣的事实是，虽然看起来这些分圆多项式的系数都只能是 $0$ 和 $\pm 1$，但是对于一般的 $n$，这个结论是不对的。第一个反例出现在 ${\Phi }_{105}(x)$，而且可以证明，随着 $n$ 的增大，它的系数可以取到任意大的值。

利用上文的 Möbius 反演式，可以总结出如下性质来简化 ${\Phi }_n(x)$ 的计算：

性质

对于分圆多项式 ${\Phi }_n(x)$，有：

1. 如果素数 $p\mid n$，则 ${\Phi }_{pn}(x)={\Phi }_n(x^p)$；
2. 如果素数 $p\perp n$，则 ${\Phi }_{pn}(x)=\frac{{\Phi }_n(x^p)}{{\Phi }_n(x)}$；
3. 特别地，如果 $n$ 是奇数，则 ${\Phi }_{2n}(x)={\Phi }_n(-x)$；
4. 对于素数 $p$，有 ${\Phi }_p(x)=1+x+\cdots +x^{p-1}$；
5. 特别地，${\Phi }_{2^k}(x)=x^{2^{k-1}}+1$。

这些性质说明，对分圆多项式的计算，重点在于那些次数是无平方因子的奇数的情形。而对于这种情形，可以用性质二逐个添加素因子；每个素因子的加入，只需要做一次多项式除法。

分圆多项式还有很多其它的性质。

定理

设 ${\Phi }_n(x)$ 为 $n>1$ 次分圆多项式，且多项式的次数是 $\phi (n)$。于是，有：

1. 多项式 ${\Phi }_n(x)$ 是回文多项式，它的 $j$ 次项系数和 $\phi (n)-j$ 次项系数相同，即 ${\Phi }_n(x)=x^{\phi (n)}{\Phi }_n(1/x)$；
2. 多项式的 $\phi (n)-1$ 次项系数等于 Möbius 函数 $-\mu (n)$；
3. 如果 $n$ 是素数幂 $p^k$，那么 ${\Phi }_n(1)=p$；否则，${\Phi }_n(1)=1$；
4. 设 $b>1$ 且 $p$ 为 ${\Phi }_n(b)$ 的素因子，则 $p\mid n$，或者 $n$ 是乘法群 $(\mathbf{Z}/p\mathbf{Z}{)}^{\times }$ 中的 $b$ 的阶，且这两种情况不能同时发生。

证明

对于前三条性质，只需要利用 Möbius 反演即可。对于 1，直接考察 ${\Phi }_n(x)$ 的 Möbius 反演形式，即 ${\Phi }_d(x)={\prod }_{d\mid n}(x^d-1{)}^{\mu (n/d)}$；对于 2，设 ${\Phi }_n(x)$ 的 $\phi (n)-1$ 次项系数为 $f(n)$，则比较 $x^n-1={\prod }_{d\mid n}{\Phi }_d(x)$ 等式两侧的 $n-1$ 次项系数可知，${\sum }_{d\mid n}f(d)=-[n=1]$，再做 Möbius 反演；对于 3，在 $x^n-1={\prod }_{d\mid n}{\Phi }_n(x)$ 两侧同时除以 ${\Phi }_1(x)=x-1$，再代入 $x=1$，即有 $n={\prod }_{d\mid n,d\ne 1}{\Phi }_n(1)$，再做 Möbius 反演。

下面证明第四条性质。首先，如果 $n$ 是乘法群 $(\mathbf{Z}/p\mathbf{Z}{)}^{\times }$ 中的 $b$ 的阶，那么 $n$ 是满足 $p\mid b^n-1$ 的正整数中最小的，故而 $p\mid {\Phi }_n(b)$。反过来，如果 $p\mid {\Phi }_n(b)$，则有 $b^n\equiv 1(\mathrm{mod}p)$；可如果 $n$ 不是乘法群 $(\mathbf{Z}/p\mathbf{Z}{)}^{\times }$ 中的 $b$ 的阶，那么设它的阶为 $k$，必然有 $k\mid n$ 且 $p\mid {\Phi }_k(b)$。此时，${\Phi }_k(x)$ 和 ${\Phi }_n(x)$ 在域 ${\mathbf{F}}_p$ 中有公共根 $b$，这说明 $x^n-1$ 有重根 $b$。这说明 $p\mid n$；否则，$x^n-1$ 与它的导数互素，所以在 ${\mathbf{F}}_p$ 上可分，不可能有重根。因而，${\Phi }_n(b)$ 的素因子 $p$ 只有两种情况：$p\mid n$，或者 $n$ 是乘法群 $(\mathbf{Z}/p\mathbf{Z}{)}^{\times }$ 中的 $b$ 的阶。这两种情况是互斥的，因为后者意味着 $n\mid p-1$。

分圆多项式还可以用于解决一些数论和代数问题。比如说分数在写成某个进制下的小数时的循环节长度，就和分圆多项式有密切的联系。对于这些具体的应用，有兴趣的读者可以参考文末的资料。

有限域

有限域（finite field），也称作 Galois 域（Galois field），就是只有有限多个元素的域。有限域的结构由其元素个数唯一确定，且它的元素个数必然是素数的幂。

定理

大小为 $q$ 的域存在，当且仅当 $q$ 具有素数幂 $p^n$ 的形式。而且，这样的域在同构意义下唯一，记作 ${\mathbf{F}}_q$。素数 $p$ 是域 ${\mathbf{F}}_q$ 的特征，正整数 $n$ 为域扩张 ${\mathbf{F}}_q/{\mathbf{F}}_p$ 的次数。最后，${\mathbf{F}}_q$ 是 ${\mathbf{F}}_p$ 上多项式 $x^q-x$ 的分裂域，且恰好包括 $x^q-x$ 的 $q$ 个互异的根。

证明

设域 $F$ 是有限域。域 $F$ 的特征必然有限，记作 $p$；故而，域 $F$ 有素子域 ${\mathbf{F}}_p$。而且，域 $F$ 必然是 ${\mathbf{F}}_p$ 上的有限扩张，扩张次数记作 $n$。作为 ${\mathbf{F}}_p$ 上的 $n$ 维向量空间，域 $F$ 有 $q=p^n$ 个元素。域 $F$ 的全体非零元构成群 $F^{\times }$，它的阶为 $q-1$，所以有 $x^{q-1}=1$。因此，$F=F^{\times }\cup \{0\}$ 的所有元素都满足 $x^q=x$，即它们是多项式 $x^q-x$ 的 $q$ 个互异的根。因此，在域 $F$ 中多项式 $x^q-x$ 有因子 ${\prod }_{\alpha \in F}(x-\alpha )$，但是这个因子的次数已经是 $q$ 且最高次项系数就等于 $1$，所以有 $x^q-x={\prod }_{\alpha \in F}(x-\alpha )$。这说明 $x^q-x$ 在 $F$ 中分裂。对于任何能够使 $x^q-x$ 分裂的域，由于 $x^q-x$ 有 $q$ 个相异的根，必然至少有 $q$ 个元素。这说明 $F$ 是使 $x^q-x$ 可以分裂的最小的域，即 $x^q-x$ 的分裂域。总而言之，大小为 $q$ 的有限域必然是它的素子域上的多项式 $x^q-x$ 的分裂域。因为分裂域在同构意义下唯一，所以大小为 $q$ 的域必然也唯一。

反过来，给定素数 $p$ 和它的幂 $q=p^n$，要说明 ${\mathbf{F}}_p$ 上的多项式 $x^q-x$ 的分裂域恰好有 $q$ 个元素，才能说明所有素数幂 $q$ 阶的域都存在。因为 ${\mathbf{F}}_p$ 上的多项式 $x^q-x$ 的分裂域总是存在，所以可以设该分裂域中多项式 $x^q-x$ 的全部根组成的集合为 $F$。现在要证明 $F$ 是域，因而它就是多项式 $x^q-x$ 的分裂域本身。但是，迭代 $n$ 次 Frobenius 自同态就可以知道 $x\mapsto x^q$ 也是自同态，因此对任意 $\alpha ,\beta \in F$ 都有 $(\alpha \pm \beta {)}^q={\alpha }^q\pm {\beta }^q$，$(\alpha \beta {)}^q={\alpha }^q{\beta }^q$ 和 $({\alpha }^{-1}{)}^q=({\alpha }^q{)}^{-1}$。因此，集合 $F$ 对加、减、乘、除都封闭，它是域。这就说明 $F$ 就是 ${\mathbf{F}}_p$ 上的多项式 $x^q-x$ 的分裂域。

推论

有限域 ${\mathbf{F}}_q$（$q>2$）中，全体非零元的和是 $0$，积是 $-1$。

证明

有限域的全体非零元恰好是多项式 $x^{q-1}-1$ 的 $q-1$ 个根，应用 Vieta 定理即可。

在素域 ${\mathbf{F}}_p$ 中，这个推论关于积的结论正是数论中的 Wilson 定理（的一部分）。

乘法结构

有限域的乘法群 ${\mathbf{F}}^{\times }=\mathbf{F}\setminus \{0\}$ 一定是循环群。

定理

域 $F$ 的乘法群的有限子群一定是循环群。

证明

设 $G$ 为域 $F$ 的乘法群的子群且 $|G|=n$。因而，$G$ 是有限 Abel 群。根据有限 Abel 群基本定理，群 $G$ 有不变因子分解 $C_{n_1}\times \cdots \times C_{n_s}$ 且 $n_1\mid \cdots \mid n_s$。所以，对于 $G$ 中的所有元素 $x$，都有 $x^{n_s}=1$。也就是说，群 $G$ 中的元素都是域 $F$ 上多项式 $x^{n_s}-1$ 的根。但是，多项式 $x^{n_s}-1$ 至多有 $n_s$ 个相异的根，即 $n\le n_s$。但是，$n_s\le n$，所以其实有 $n_s=n$。这说明 $G\cong C_{n_s}$，即群 $G$ 是循环群。

推论

有限域 ${\mathbf{F}}_q$ 的乘法群 ${\mathbf{F}}_q^{\times }\cong C_{q-1}$。

循环群 ${\mathbf{F}}_q^{\times }$ 中有 $\phi (q-1)$ 个生成元，它们称为有限域的本原元；其中，$\phi (n)$ 是 欧拉函数。

本原元

有限域 ${\mathbf{F}}_q$ 的乘法群的生成元，称为 ${\mathbf{F}}_q$ 的 本原元（primitive element）。

单扩张中的本原元和有限域中的本原元并不相同

尽管单扩张中的本原元和有限域中的本原元的名称一致，两者并不相同。单扩张中的本原元是相应的单扩张的生成元，而有限域中的本原元是相应的乘法群（作为循环群）的生成元。有限域作为它的素子域的单扩张的本原元，未必是有限域本身的本原元。例如，${\mathbf{F}}_{25}\cong {\mathbf{F}}_5[x]/(x^2+x+1)$ 中，$\overline{x}$ 是域扩张的本原元，但是并不是域 ${\mathbf{F}}_{25}$ 的本原元，因为它的阶数是 $3$。

${\mathbf{F}}_q$ 中的本原元和模 $q$ 的原根也不相同

对于奇数特征的有限域 ${\mathbf{F}}_q$，总是存在模 $q$ 的 原根（primitive root）。但是，不应将它与有限域 ${\mathbf{F}}_q$ 中的本原元（primitive element）混淆。虽然它们都是相应的乘法结构作为循环群时的生成元，但是 $(\mathbf{Z}/q\mathbf{Z}{)}^{\times }$ 和 ${\mathbf{F}}_q$ 在 $q$ 本身不是素数的情况下并不相同。比如，前者的阶是 $\phi (q)$ 而后者的阶是 $q-1$，两个乘法群的大小就不相同。

设 $\alpha$ 是有限域 ${\mathbf{F}}_q$ 的一个本原元。那么，对于所有 $x\in {\mathbf{F}}_q$ 都存在唯一的自然数 $k<q-1$ 使得 $x={\alpha }^k$；这个 $k$ 就称为 ${\mathbf{F}}_q$ 上元素 $x$ 关于基 $\alpha$ 的 离散对数（discrete logarithm）。和 ${\mathbf{F}}_p$ 上的情形一致，离散对数的算法 的复杂度都比较高。

通过乘法运算，本原元已经可以生成域的全体非零元素。这说明，有限域作为它的子域的扩张，一定是单扩张。

定理

对于有限域 ${\mathbf{F}}_q$，设 $F$ 为 ${\mathbf{F}}_q$ 的子域，则 ${\mathbf{F}}_q$ 是 $F$ 上的单代数扩张；又设 $\alpha$ 为 ${\mathbf{F}}_q$ 的本原元，则 ${\mathbf{F}}_q=F(\alpha )$。

本原元的极小多项式是有限域的子域上的不可约多项式。

包含关系

有限域的子域也是有限域。有限域之间的包含关系，也完全由它们的阶决定。

定理

设 ${\mathbf{F}}_q$ 和 ${\mathbf{F}}_r$ 是有限域，则 ${\mathbf{F}}_r$ 是 ${\mathbf{F}}_q$ 的子域，当且仅当存在 $k$ 使得 $q=r^k$。换句话说，${\mathbf{F}}_{p^d}$ 是 ${\mathbf{F}}_{p^n}$ 的子域，当且仅当 $d\mid n$。

证明

如果 ${\mathbf{F}}_r$ 是 ${\mathbf{F}}_q$ 的子域，那么两者必然有相同的特征 $p$。域扩张 ${\mathbf{F}}_q/{\mathbf{F}}_r$、${\mathbf{F}}_r/{\mathbf{F}}_p$ 和 ${\mathbf{F}}_q/{\mathbf{F}}_p$ 都是单代数扩张，分别记它们的扩张次数为 $k,d,n$，则扩张次数必然满足 $n=kd$。而且，$r=p^d$ 和 $q=p^n$，并成立 $q=p^n=p^{kd}=(p^d{)}^k=r^k$。

反过来，要证明对于所有 $d\mid n$，${\mathbf{F}}_{p^d}$ 都是 ${\mathbf{F}}_{p^n}$ 的子域。记 $r=p^d$ 且 $q=p^n$。设 $F$ 为有限域 ${\mathbf{F}}_q$ 中方程 $x^r-x=0$ 的全体根的集合。通过 Frobenius 自同态可以证明，集合 $F$ 必然构成域；关键是要证明，这样的根恰好有 $r$ 个，所以才有 $F\cong {\mathbf{F}}_r$。因为 $d\mid n$，所以 $(p^d-1)\mid (p^n-1)$，所以 $(x^{p^d-1}-1)\mid (x^{p^n-1}-1)$，也就是 $(x^r-x)\mid (x^q-x)$。所以，$x^r-x$ 在 ${\mathbf{F}}_q$ 上分裂，故而在 ${\mathbf{F}}_q$ 内有 $r$ 个不同的根。这就说明 $F\cong {\mathbf{F}}_r$ 是 ${\mathbf{F}}_q$ 的子域。

这一定理说明，有限域 ${\mathbf{F}}_{p^n}$ 的包含关系，对应着域的阶 $p^n$ 中的指数 $n$ 之间的整除关系。所有特征为 $p$ 的有限域 ${\mathbf{F}}_{p^n}$ 之间形成的格，也就同构于整数 $n$ 在整除关系下形成的格。当然，为了让有限域 ${\mathbf{F}}_{p^n}$ 之间的交集等运算有意义，需要将所有特征为 $p$ 的域都嵌入到 ${\mathbf{F}}_p$ 的代数闭包中。

定理

设 $F$ 为 ${\mathbf{F}}_p$ 的代数闭包，则域 $F$ 中多项式 $x^{p^n}-x$ 的根的集合构成有限域 ${\mathbf{F}}_{p^n}$。那么，有：

1. $F={\bigcup }_{n=1}^{\infty }{\mathbf{F}}_{p^n}$，即 ${\mathbf{F}}_p$ 的代数闭包就是所有特征为 $p$ 的有限域的并集；
2. 全体特征为 $p$ 的有限域 ${\mathbf{F}}_{p^n}$ 在包含关系下形成的格，同构于整数 $n$ 在整除关系下形成的格。特别地，${\mathbf{F}}_{p^n}$ 和 ${\mathbf{F}}_{p^m}$ 的交集 ${\mathbf{F}}_{p^n}\cap {\mathbf{F}}_{p^m}={\mathbf{F}}_{p^{\gcd (n,m)}}$，而同时包含 ${\mathbf{F}}_{p^n}$ 和 ${\mathbf{F}}_{p^m}$ 的最小的域 ${\mathbf{F}}_{p^n}{\mathbf{F}}_{p^m}={\mathbf{F}}_{p^{\mathrm{lcm}(n,m)}}$。

证明

关键在于证明第一部分，即 ${\bigcup }_{n=1}^{\infty }{\mathbf{F}}_{p^n}$ 是 $F_p$ 的代数闭包。第二部分是前面关于有限域的子域的定理的简单推论。

注意到，任取 $\alpha \in {\bigcup }_{n=1}^{\infty }{\mathbf{F}}_{p^n}$，必然存在 $n\in {\mathbf{N}}_{+}$ 使得 $\alpha \in {\mathbf{F}}_{p^n}$ 成立，故而 $\alpha$ 是 ${\mathbf{F}}_p$ 上的代数元；因而，${\bigcup }_{n=1}^{\infty }{\mathbf{F}}_{p^n}$ 是 ${\mathbf{F}}_p$ 的代数扩张。对于任何 ${\mathbf{F}}_p$ 上的 $m$ 次多项式 $f(x)$，它在代数闭包 $F$ 中有至多 $m$ 个不同的根 $\{{\alpha }_i{\}}_{i=1}^m$。设根 ${\alpha }_i$ 的极小多项式次数为 $n_i$，则 ${\alpha }_i$ 必然包含在域 ${\mathbf{F}}_{p^{n_i}}$ 内；故而，$f(x)$ 的所有根都在 $\alpha \in {\bigcup }_{n=1}^{\infty }{\mathbf{F}}_{p^n}$ 中，亦即 $f(x)$ 在 $\alpha \in {\bigcup }_{n=1}^{\infty }{\mathbf{F}}_{p^n}$ 上分裂。根据代数闭包的定义，$\alpha \in {\bigcup }_{n=1}^{\infty }{\mathbf{F}}_{p^n}$ 就是 ${\mathbf{F}}_p$ 的代数闭包。

自同构群

有限域 ${\mathbf{F}}_q$ 上的子域都是形如 $x^r-x$ 的多项式的根的集合。换言之，它们都是某个映射 $x\mapsto x^r$ 的不动点集合。这其实揭示了有限域的子域和自同构群的子群之间的深刻对应关系。

特征为 $p$ 的域上都有 Frobenius 自同态 ${\sigma }_p:x\mapsto x^p$。对于有限域 ${\mathbf{F}}_q$ 的情形，这也是自同构；这说明有限域 ${\mathbf{F}}_q$ 都是完美域。域 ${\mathbf{F}}_q$ 的自同构群就是 $n$ 阶循环群 $⟨{\sigma }_p⟩$，它的一个生成元就是 Frobenius 自同态 ${\sigma }_p$。

定理

有限域 ${\mathbf{F}}_q$ 的自同构群 $\mathrm{Aut}({\mathbf{F}}_q)=⟨{\sigma }_p⟩$ 是 $n$ 阶循环群，且生成元 ${\sigma }_p$ 是 Frobenius 自同态 $x\mapsto x^p$。

证明

首先，Frobenius 自同态 ${\sigma }_p$ 在有限域 ${\mathbf{F}}_q$ 上是自同构，因为有限集合上的单射必然也是满射。因此，${\sigma }_p\in \mathrm{Aut}({\mathbf{F}}_q)$。

然后，${\sigma }_p$ 的阶是 $n$。这是因为对于所有 $x\in {\mathbf{F}}_q$ 都有 ${\sigma }_p^n(x)=x^{p^n}=x$，故而 $x^{p^n}$ 是恒等映射；而且对于任何 $k<n$ 都有 ${\sigma }_p^k$ 不是恒等映射，否则 ${\mathbf{F}}_q$ 的元素都得是 $x^{p^k}-x$ 的根，这不可能。

最后，$\mathrm{Aut}({\mathbf{F}}_q)$ 至多有 $n$ 个元素。设 $\alpha$ 为 ${\mathbf{F}}_q$ 的一个本原元，则自同构 $\sigma \in \mathrm{Aut}({\mathbf{F}}_q)$ 由它在 $\alpha$ 处的取值 $\sigma (\alpha )$ 唯一确定。但是，$\sigma$ 必须将 $\alpha$ 映射到它的共轭元；否则，$\alpha$ 和 $\sigma (\alpha )$ 不再是同一个极小多项式的根。这样的共轭元只有 $n$ 个，这就说明 $\mathrm{Aut}({\mathbf{F}}_q)$ 也至多有 $n$ 个元素。

因此，$\mathrm{Aut}({\mathbf{F}}_q)$ 中的 $n$ 个元素正是 $⟨{\sigma }_p⟩$。定理得证。

自同构群 $\mathrm{Aut}({\mathbf{F}}_q)$ 的子群和有限域 ${\mathbf{F}}_q$ 上的子域一一对应。

定理

设 ${\mathbf{F}}_q$ 为有限域，$\mathcal{F}$ 为它的全体子域，$\mathcal{G}$ 为它的自同构群 $\mathrm{Aut}({\mathbf{F}}_q)$ 的全体子群。对此，有：

1. 对于 $F\in \mathcal{F}$，设 $\mathrm{Aut}({\mathbf{F}}_q/F)$ 为 $\mathrm{Aut}({\mathbf{F}}_q)$ 中保持 $F$ 不变的自同构的集合，即 $\mathrm{Aut}({\mathbf{F}}_q/F)=\{\sigma \in \mathrm{Aut}({\mathbf{F}}_q):\forall x\in F(\sigma (x)=x)\}$，则 $\mathrm{Aut}({\mathbf{F}}_q/F)\le \mathrm{Aut}({\mathbf{F}}_q)$；
2. 对于 $G\in \mathcal{G}$，设 $F^G$ 为 $G$ 中的所有自同构的不动点集合的交集，即 $F^G=\{x\in {\mathbf{F}}_q:\forall \sigma \in G(\sigma (x)=x)\}$，则 $F^G$ 为 ${\mathbf{F}}_q$ 的子域；
3. 映射 $F\to \mathrm{Aut}({\mathbf{F}}_q/F)$ 和映射 $G\to F^G$ 互为逆映射，且是 $\mathcal{F}$ 和 $\mathcal{G}$ 之间的一一对应；
4. 这个一一对应，将子域之间的扩张关系映射为子群之间的包含关系，即对于任何 $F_1\subseteq F_2$，都有 $\mathrm{Aut}({\mathbf{F}}_q/F_2)\le \mathrm{Aut}({\mathbf{F}}_q/F_1)$。

这个结论是一般的 Galois 理论的基本定理的特殊情形，它将域扩张和群论的内容联系起来，从而可以通过群论的方法解决域扩张的问题。

不可约多项式

有限域 ${\mathbf{F}}_q$ 上的不可约多项式十分容易确定。因为有限域 ${\mathbf{F}}_q$ 上的每个 $n$ 次不可约多项式都对应着 $n$ 次代数扩张，而这样的扩张是唯一的，故而所有 $n$ 次不可约多项式的根都可以在 ${\mathbf{F}}_{q^n}$ 中找到。这说明，${\mathbf{F}}_q$ 上的 $n$ 次不可约多项式必然是 $x^{q^n}-x$ 的因子。要确定有限域 ${\mathbf{F}}_q$ 上的所有 $n$ 次不可约多项式，需要考察 $x^{q^n}-x$ 在 ${\mathbf{F}}_q$ 上的因式分解。这和分圆多项式的情形十分类似。

有理数域 ${\mathbf{F}}_q$ 上的代数元可以根据其极小多项式的次数分类。设 $P_n$ 是极小多项式次数恰为 $n$ 的代数元集合，则

$${\mathbf{F}}_{q^n}=\bigcup _{d\mid n}{P}_d.$$

这对应着因式分解

$$x^{q^n}-x=\prod _{d|n}\prod _{\zeta \in P_d}(x-\zeta ).$$

因为 $n$ 次不可约多项式有 $n$ 个根，而且这些根的极小多项式的次数都是 $n$，所以 $n$ 次不可约多项式必然是多项式

$$\prod _{\zeta \in P_n}(x-\zeta )=\prod _{d\mid n}{\left(x^{q^d}-x\right)}^{\mu (n/d)}$$

的因子；这个表达式是对前面的因式分解应用 Möbius 反演 得到的。因为这个多项式的次数是

$$\sum _{d\mid n}\mu (d)q^{n/d},$$

所以，${\mathbf{F}}_q$ 上的 $n$ 次不可约首一多项式共计

$$\frac{1}{n}\sum _{d\mid n}\mu (d)q^{n/d}$$

个。这恰为不计旋转意义下，$q$ 个颜色的珠子能够串成的长度为 $n$ 的项链的种类个数（证明），所以又称为项链多项式（necklace polynomial）。

定理

有限域 ${\mathbf{F}}_q$ 上存在任意次数的不可约多项式。

因为有限域上的不可约多项式有着简单的结构，这使得有限域上的多项式的因式分解十分容易。比如，要确定给定多项式的全体 $n$ 次不可约因子，只要求解给定多项式与 $x^{q^n}-x$ 的最大公因子即可 ⁶。类似地，只要 $n$ 次多项式对所有的 $k<n$ 都与多项式 $x^{q^k}-1$ 互素，就可以断定该 $n$ 次多项式在 ${\mathbf{F}}_q$ 上不可约。

前文已经指出，有限域上的不可约多项式的根未必是相应扩域作为有限域的本原元。有限域 ${\mathbf{F}}_q$ 的本原元在它的素子域 ${\mathbf{F}}_p$ 上的极小多项式也称为域 ${\mathbf{F}}_p$ 上的 本原多项式⁷（primitive polynomial）。用这样的多项式实现扩域，就可以保证 $\overline{x}$ 必然是扩域中的本原元。域 ${\mathbf{F}}_p$ 上的 $n$ 次本原多项式可以通过在 ${\mathbf{F}}_p$ 上对分圆多项式 ${\Phi }_n(x)$ 进行因式分解得到。

定理

设 $p$ 为素数，$n$ 为正整数，且 $p\perp n$。又设 $d$ 是乘法群 $(\mathbf{Z}/n\mathbf{Z}{)}^{\times }$ 中元素 $p$ 的阶。那么，分圆多项式 ${\Phi }_n(x)$ 在域 ${\mathbf{F}}_p$ 可以分解为 $\frac{\phi (n)}{d}$ 个 ${\mathbf{F}}_p$ 上的 $d$ 次本原多项式的乘积。特别地，分圆多项式 ${\Phi }_n(x)$ 在域 ${\mathbf{F}}_p$ 上不可约，当且仅当 $p$ 是模 $n$ 的原根。

证明

如果注意到，$n$ 次分圆多项式的根是所有 ${\mathbf{F}}_p$ 的 $n$ 次本原单位根，而 $n$ 次本原单位根的极小多项式的次数 $d$ 就是它的共轭（包括自身）的数量，也就等于它在自同构群 $⟨{\sigma }_p⟩$ 下的轨道长度，那么就可以知道 $d$ 是 $\{{\zeta }^i:i\perp n\}$ 中映射 ${\zeta }^i\mapsto {\zeta }^{ip}$ 的循环子群的轨道长度，亦即乘法群 $(\mathbf{Z}/n\mathbf{Z}{)}^{\times }$ 中元素 $p$ 的阶。如果不想依赖于 Galois 理论，也可以通过说明 $d$ 是最小的正整数使得 $(x^n-1)\mid (x^{p^d-1}-1)$ 成立来证明此事。其余结论显然。

虽然不可约多项式对于有限域的实现很重要，但是要找到有限域 ${\mathbf{F}}_q$ 上的一个 $n$ 次不可约多项式却并没有较好的确定性的方法。在一般的情况下，可以使用随机方法生成这样的不可约多项式。因为所有 $n$ 次首一多项式中，不可约多项式占的比例是 $\Theta (1/n)$ 的，所以可以先随机生成一个 $n$ 次首一多项式再判断它是否可约。这样做可以在生成期望 $\Theta (n)$ 个首一多项式后找到一个不可约多项式。当然，这样生成的不可约多项式未必是本原多项式，系数也未必是简单的。在实际操作中，如果有限域的大小提前给定，往往可以通过查表 ⁸ 的方式找到系数简单的本原多项式，方便后续的计算。

参考实现

本节提供一个朴素的有限域的实现，仅供参考。代码中实现了随机生成不可约多项式的方法。

参考实现

#include <iostream>
#include <random>
#include <vector>
 
class FiniteField {
  int p, k;
  std::vector<int> mod;  // Monic.
 
  // Remove leadings zeros of a polynomial.
  static void trim(std::vector<int>& poly) {
    int m = poly.size();
    for (; m && !poly[m - 1]; --m);
    poly.resize(m);
  }
 
  // Binary exponentiation mod p.
  int pow(int a, int b) const {
    int res = 1, po = a;
    while (b) {
      if (b & 1) res = (long long)res * po % p;
      po = (long long)po * po % p;
      b >>= 1;
    }
    return res;
  }
 
  // Multiplicative inverse mod p.
  int inv(int a) const { return pow(a, p - 2); }
 
  // Polynomial GCD. Inputs are supposed to have no leading zeros.
  std::vector<int> poly_gcd(const std::vector<int>& lhs,
                            const std::vector<int>& rhs) const {
    if (lhs.size() < rhs.size()) {
      return poly_gcd(rhs, lhs);
    } else if (rhs.size()) {
      auto rem = lhs;  // remainder.
      long long v = inv(rhs.back());
      for (int i = rem.size() - rhs.size(); i >= 0; --i) {
        auto d = v * (p - rem[i + rhs.size() - 1]) % p;
        for (int j = 0; j < rhs.size(); ++j) {
          rem[i + j] = (rem[i + j] + d * rhs[j]) % p;
        }
      }
      trim(rem);  // Remove leading zeros.
      return poly_gcd(rhs, rem);
    } else {
      return lhs;
    }
  }
 
  // Polynomials Ex-GCD. Inputs are supposed to have no leading zeros.
  void poly_ex_gcd(const std::vector<int>& lhs, const std::vector<int>& rhs,
                   std::vector<int>& x, std::vector<int>& y) const {
    if (lhs.size() < rhs.size()) {
      poly_ex_gcd(rhs, lhs, y, x);
    } else if (rhs.size()) {
      std::vector<int> quo(lhs.size() - rhs.size() + 1);  // quotient.
      auto rem = lhs;                                     // remainder.
      long long v = inv(rhs.back());
      for (int i = rem.size() - rhs.size(); i >= 0; --i) {
        quo[i] = v * rem[i + rhs.size() - 1] % p;
        long long d = p - quo[i];  // d = -quo[i].
        for (int j = 0; j < rhs.size(); ++j) {
          rem[i + j] = (rem[i + j] + d * rhs[j]) % p;
        }
      }
      trim(rem);  // Remove leading zeros.
      // Recursively ex_gcd.
      poly_ex_gcd(rhs, rem, y, x);
      // y -= a/b*x.
      if (y.size() < quo.size() + x.size() - 1) {
        y.resize(quo.size() + x.size() - 1, 0);
      }
      for (int i = 0; i < quo.size(); ++i) {
        for (int j = 0; j < x.size(); ++j) {
          y[i + j] = (y[i + j] - (long long)quo[i] * x[j]) % p;
          if (y[i + j] < 0) y[i + j] += p;
        }
      }
      trim(y);  // Remove leading zeros.
    } else {
      // x = 1, y = 0.
      x.assign(1, inv(lhs.back()));
      y.clear();
    }
  }
 
 public:
  // Class for Finite Field Elements.
  struct Element {
    const FiniteField* gf;
    std::vector<int> a;
 
    // Element initialization as zero.
    Element(const FiniteField* gf) : gf(gf), a(gf->k) {}
 
    // Element initialization from the numeric representation.
    Element(const FiniteField* gf, int id) : gf(gf), a(gf->k) {
      for (int i = 0; i < gf->k; ++i) {
        a[i] = id % gf->p;
        id /= gf->p;
      }
    }
 
    // Generate the numeric representation from an element.
    int idx() const {
      int id = 0;
      for (int i = gf->k - 1; i >= 0; --i) {
        id = id * gf->p + a[i];
      }
      return id;
    }
 
    // Access the i-th coefficient.
    int& operator[](int i) { return a[i]; }
 
    // Addition.
    Element& operator+=(const Element& rhs) {
      for (int i = 0; i < gf->k; ++i) {
        a[i] += rhs.a[i];
        if (a[i] >= gf->p) a[i] -= gf->p;
      }
      return *this;
    }
 
    // Addition.
    Element operator+(const Element& rhs) const {
      Element res(*this);
      res += rhs;
      return res;
    }
 
    // Subtraction.
    Element& operator-=(const Element& rhs) {
      for (int i = 0; i < gf->k; ++i) {
        a[i] -= rhs.a[i];
        if (a[i] < 0) a[i] += gf->p;
      }
      return *this;
    }
 
    // Subtraction.
    Element operator-(const Element& rhs) const {
      Element res(*this);
      res -= rhs;
      return res;
    }
 
    // Multiplication by a scalar.
    Element& operator*=(int x) {
      for (int i = 0; i < gf->k; ++i) {
        a[i] = (long long)a[i] * x % gf->p;
      }
      return *this;
    }
 
    // Multiplication by a scalar.
    Element operator*(int x) const {
      Element res(*this);
      res *= x;
      return res;
    }
 
    // Multiplication by x.
    Element& shift() {
      long long d = gf->p - a.back();  // d = -a[k-1].
      for (int i = gf->k - 1; i >= 0; --i) {
        a[i] = ((i ? a[i - 1] : 0) + d * gf->mod[i]) % gf->p;
      }
      return *this;
    }
 
    // Multiplication.
    Element& operator*=(const Element& rhs) {
      Element prod(*this);
      *this *= rhs.a[0];
      for (int j = 1; j < gf->k; ++j) {
        prod.shift();
        *this += prod * rhs.a[j];
      }
      return *this;
    }
 
    // Multiplication.
    Element operator*(const Element& rhs) const {
      Element res(*this);
      res *= rhs;
      return res;
    }
 
    // Binary exponentiation.
    Element pow(int b) const {
      Element res(gf, 1);
      Element po(*this);
      while (b) {
        if (b & 1) res *= po;
        po = po * po;
        b >>= 1;
      }
      return res;
    }
 
    // Multiplicative inverse.
    Element inv() const {
      Element res(gf);
      auto& x = res.a;
      std::vector<int> y;
      auto lhs = a;
      trim(lhs);
      auto rhs = gf->mod;
      gf->poly_ex_gcd(lhs, rhs, x, y);
      x.resize(gf->k);
      return res;
    }
 
    // Division.
    Element& operator/=(const Element& rhs) {
      *this *= rhs.inv();
      return *this;
    }
 
    // Division.
    Element operator/(const Element& rhs) const {
      Element res(*this);
      res /= rhs;
      return res;
    }
  };
 
 private:
  // Check whether the current MOD is irreducible.
  bool checkIrreducible() const {
    Element f(this, p);
    for (int j = 1; j < k; ++j) {
      // F = X^{p^j} mod MOD.
      f = f.pow(p);
      // G = X^{p^j}-X mod MOD.
      auto g = f.a;
      g[1] = g[1] ? g[1] - 1 : p - 1;
      trim(g);
      // H = MOD.
      auto h = mod;
      // Reducible if deg(GCD(G,H))>0.
      if (poly_gcd(h, g).size() > 1) return false;
    }
    return true;
  }
 
 public:
  FiniteField(int p, int k) : p(p), k(k), mod(k + 1, 1) {
    do {  // Randomly generate a polynomial.
      for (int i = 0; i < k; ++i) {
        mod[i] = rand() % p;
      }
    } while (!checkIrreducible());
  }
};
 
int main() {
  int p = 13331, k = 50;
  FiniteField gf(p, k);
  FiniteField::Element e1(&gf, rand() + 1);
  FiniteField::Element e2(&gf, rand() + 1);
  FiniteField::Element e3(&gf, rand() + 1);
  // Test Frobenius endomorphism.
  std::cout
      << ((e1 * e2 + e3).pow(p) - e1.pow(p) * e2.pow(p) - e3.pow(p)).idx();
  // Test inverse.
  std::cout << ((e1 * e2).inv() - e1.inv() / e2).idx();
  return 0;
}

密码学上用的最多的是特征为 $2$ 的有限域。对于这类有限域，可以将域中的元素存储为 01 串，用位运算的方式实现域中的操作。

应用

本节列举一些域扩张在算法竞赛中的应用。最主要的情形，就是在对域上的算术表达式进行计算时，需要在中间过程引入一些原本的域中并不存在的元素，从而使得直接的计算成为可能。读者应当熟悉利用复数解决实数问题的情形，这就是实数域上的扩张的例子；读者相对陌生的，可能是有限域上的扩张。所以，这里主要讨论有限域上的扩张，尤其是素域 ${\mathbf{F}}_p$ 上的扩张。

有些情形下，域扩张可以降低计算的复杂度，故而是必要的，例如实数域上的 快速傅里叶变换；有些情形下，域扩张只是众多解决问题方法中的一种，且通常有类似复杂度的方法可以避免使用域扩张，例如马上要提到的对斐波那契数列的计算。读者在理解这些应用的同时，应当比较不同方法的优劣，从而能够在解决问题时选择合适的方法。

斐波那契数列

对于 斐波那契数列 的计算，常见方法有 $O(n)$ 的线性递推和 $O(\log n)$ 的矩阵快速幂。实际上，它还可以通过域扩张的方法加以解决，时间复杂度同样是 $O(\log n)$。斐波那契数列有通项公式：

$$f(n)=\frac{1}{\sqrt{5}}\left({\left(\frac{1+\sqrt{5}}{2}\right)}^n-{\left(\frac{1-\sqrt{5}}{2}\right)}^n\right).$$

现在要计算 $f(n)$ 在素数模 $p\ne 5$ 下的值 ⁹。将这个问题转化为有限域 ${\mathbf{F}}_p$ 上的计算，首先要解决的就是 $\sqrt{5}$ 在 ${\mathbf{F}}_p$ 中的意义。从代数角度看，它就是元素 $5$ 的平方根。因而，如果 ${\mathbf{F}}_p$ 中存在 $5$ 的平方根，即 $5$ 是模 $p$ 的二次剩余的时候，可以直接计算其二次剩余并带入计算；否则，就需要在扩域 ${\mathbf{F}}_p(\sqrt{5})\cong {\mathbf{F}}_p[x]/(x^2-5)$ 下进行计算。

当然，在扩域中进行计算的时候，没有必要一定加入 $\sqrt{5}$。比如说，对于斐波那契数列，也可以设 $\varphi$ 是多项式 $x^2-x-1$ 的根，从而 $f(n)$ 可以写作

$$f(n)=\frac{{\varphi }^n-(-\varphi {)}^{-n}}{2\varphi -1}=\frac{{\varphi }^n-(1-\varphi {)}^n}{2\varphi -1}.$$

如果 $5$ 并非模 $p$ 下的二次剩余，多项式 $x^2-x-1$ 就是不可约的。此时，可以在扩域 ${\mathbf{F}}_p(\theta )\cong {\mathbf{F}}_p[x]/(x^2-x-1)$ 上进行计算，能够得到和前文一致的结果。

计算斐波那契数列的方法当然可以推广到别的情形。但是，有一点应当注意：有限域上多项式的不可约性和有理数域并不一致。譬如 $x^4-10x^2+1$，它在 $\mathbf{Q}$ 上是不可约的，相应的分裂域是 $\mathbf{Q}(\sqrt{2}+\sqrt{3})=\mathbf{Q}(\sqrt{2},\sqrt{3})$；但是在 ${\mathbf{F}}_p$ 中，如果 $2$ 和 $3$ 都不是模 $p$ 的二次剩余，那么它是两个不可约多项式的乘积，亦即在扩域 ${\mathbf{F}}_p(\sqrt{2})$ 中就已经存在平方根 $\sqrt{3}$ 而不需要进一步扩张。

推广到环上的「扩张」

正如上一节所展示的那样，域的扩张有着各种各样的限制。对于斐波那契数列的计算，只用扩域的方法只能解决模数 $p$ 是素数且 $5$ 不是 $p$ 的二次剩余的情形。但是应当注意，在 代数扩张 一节中的论述表明，如果不要求在扩张后的结构中做除法运算，那么可以对环进行扩张 ¹⁰。本节以任意模数 $n$ 下斐波那契数列的计算为例，简要讨论这种方法。其他的不涉及过多除法运算的常见情景，包括行列式的计算、快速傅里叶变换等，有必要的时候都可以尝试应用这种方法。

设 $m$ 为任意正整数，$f(n)$ 为斐波那契数列的第 $n$ 项。问题是要计算 $f(n)\mathrm{mod}m$ 的值。原则上，需要在 $\mathbf{Z}/m\mathbf{Z}$ 上进行计算。但是，正如上节所表明的，在不同模数下，多项式 $x^2-x-1$ 的可约性和有无重根的情形不一致，所以斐波那契数列的通项可能相差甚远。而且，如果本身 $\mathbf{Z}/m\mathbf{Z}$ 并不是域，扩张后的元素也往往没有合法的逆（比如模 $5$ 的时候，分母 $\sqrt{5}$ 直接就是零）。虽然有着诸多问题，但是其实在系数对 $m$ 取模的条件下，计算余数

$$(1-x{)}^n-x^n\mathrm{mod}{x}^2-x-1$$

的常数项即可。比对上文中的通项公式，这个做法的合理性是显然的：这似乎就是在「扩张」$(\mathbf{Z}/m\mathbf{Z})[x]/(x^2-x-1)$ 中计算

$$f(n)=\frac{(1-\varphi {)}^n-{\varphi }^n}{1-2\varphi }$$

的值，且 $\varphi$ 是 $x^2-x-1$ 的根。

虽然没有那么显然，但是这个做法也是合法的。注意到，在有理数域的扩张 $\mathbf{Q}(\varphi )\cong \mathbf{Q}[x]/(x^2-x-1)$ 中，通项公式成立。这就说明，在 $\mathbf{Q}[x]$ 中，

$$(1-x{)}^n-x^n\equiv f(n)(1-2x)(\mathrm{mod}{x}^2-x-1)$$

成立。这只涉及到整系数多项式，因而在 $\mathbf{Z}[x]$ 中也成立。写成带余除法，等式两边的系数都对 $m$ 取模，就得到 $(\mathbf{Z}/m\mathbf{Z})[x]$ 上的恒等式。这个结论对于任意 $m$ 都成立。

一般的情况下，如果某个表达式可以在有理数域 $\mathbf{Q}$ 的扩域上进行计算，那么就一定可以通过约去分母的方式得到 $\mathbf{Z}[x]$ 上的结论，再对 $m$ 取模就得到 $(\mathbf{Z}/m\mathbf{Z})[x]$ 上的结论。这种思路能够行得通的关键在于，约去分母这一步不应该造成「不可挽回」的后果。比如，对于斐波那契数列的计算，如果不用常数项的系数，而是用一次项的系数，那么因为系数有因子 $2$，那么 $2$ 在模 $m$ 是偶数的情况下就没有逆元，没有办法恢复 $f(n)$ 的值；再比如，同样是斐波那契数列的计算，如果使用带有 $(-\varphi {)}^{-n}$ 项的通项公式，那么约去分母的步骤会引入难以处理的因子，从而无法从取余后的结果得到结论。因而，对于计算过程的选择，是能够应用这一技巧的关键。

Cipolla 算法

这是利用有限域的扩域进行计算的典型例子。对于模 $p\ne 2$ 下的二次剩余 $a$，要找到它的平方根，即使得 $x^2\equiv a(\mathrm{mod}p)$ 成立的 $x$。虽然这是 ${\mathbf{F}}_p$ 上的问题，但是 Cipolla 算法 在有限域 ${\mathbf{F}}_{p^2}$ 上进行计算。本节使用域论的语言对这个算法进行说明。初等数论的证明可以参考所给链接。

具体来说，Cipolla 算法首先选择 $r$ 使得 $r^2-a$ 是模 $p$ 的二次非剩余，这意味着 $x^2-(r^2-a)$ 是不可约多项式。因而，令 $u=r^2-a$，可以考虑扩域 ${\mathbf{F}}_p(\sqrt{u})$。因为 Frobenius 自同态只能将元素映射到它的共轭，而这样的共轭在二次扩张中是唯一的，即有 $(r-\sqrt{u}{)}^p=r+\sqrt{u}$。故而，$(r-\sqrt{u}{)}^{p+1}=(r+\sqrt{u})(r-\sqrt{u})=r^2-u=a$。所以，要确定平方根，只要计算 $(r-\sqrt{u}{)}^{(p+1)/2}$ 就好了。这个值必然位于 ${\mathbf{F}}_p$ 中，因为 $x^2-a$ 的分裂域就是 ${\mathbf{F}}_p$ 本身。

习题

最后，列举一些直接应用本文内容的题目，以便加深理解。但应注意，很多内容并不是算法竞赛的常规考点。

• 分圆多项式：
  • Luogu P1520 因式分解
  • Gym102114C Call It What You Want
• 有限域：
  • Luogu P3923 大学数学题
  • [COTS 2021] 菜 Jelo
  • CF1310F. Bad Cryptography
  • LOJ 178. 多项式求根
• 域扩张：
  • [Oleksandr Kulkov Contest 2] Problem A. Square Root Partitioning
  • CF1103E. Radix Sum

参考资料与注释

• Dummitt, D.S. and Foote, R.M. (2004) Abstract Algebra. 3rd Edition, John Wiley & Sons, Inc.
• Milne, J.S. Fields and Galois Theory.
• Factorization of polynomials - Wikipedia
• Factorization of polynomials over finite fields - Wikipedia
• Cyclotomic Polynomial - Wikipedia
• Brett Porter’s Notes on Cyclotomic Polynomials
• Jordan Bell’s Notes on Cyclotomic Polynomials
• Michel Waldschmidt. An introduction to the theory of finite fields
• Finite Field Arithmetic - Wikipedia

Footnotes

1. 这是因为域 $E$ 的幺元 $1_E$ 必然满足 $F$ 上的关系 $x^2-x=0$，而后者在域 $F$ 内只有两个根 $0_F$ 和 $1_F$，由于域的定义要求 $1_E\ne 0_E$，就必然有 $1_E=1_F$ 和 $0_E=0_F$。 ↩

2. 用范畴论的语言来说，就是 $\mathbf{Z}$ 是幺环范畴的 始对象。 ↩

3. 严格地说，这里指的是多项式环 $R[x]$ 的 万有性质（universal property）。 ↩

4. 此处的多项式环有无限多个不定元。要定义这样的多项式环，首先要定义单项式。设不定元的集合为 $X$，则它上面的单项式是全体只在有限多个不定元处取值不为零的函数 $\alpha :X\to \mathbf{N}$，可以记作 $x_{i_1}^{\alpha (i_i)}\cdots x_{i_k}^{\alpha (i_k)}$，其中，$i_1,\cdots ,i_k$ 是所有 $\alpha$ 取值不为零的不定元的指标。多项式是所有有限多个单项式的线性组合。它们在相应定义的加法和乘法运算下成为环。对于有限多个不定元的情形，可以证明这种定义与 多元多项式环 一节的递归定义得到的结果是一致的。 ↩

5. 虽然名字是代数基本定理，这个结论并不是纯代数的，这是因为实数域的构造需要通过拓扑结构进行。 ↩

6. 这样的说法有失严谨，因为还会得到次数 $d\mid n$ 的不可约因子。但是，由于算法实现时通常会从较小的次数的因子开始分离，在分离 $n$ 次不可约多项式因子时，较小的因子应该已经分离完了，所以这说法也是可以接受的。 ↩

7. 不要把这里的名称和多项式理论中的本原多项式（即所有系数的最大公因子是一的多项式）混淆。 ↩

8. 比如，Hansen, T., & Mullen, G. L. (1992). Primitive polynomials over finite fields. Mathematics of computation, 59(200), 639-643 的附录就提供了这样的列表。 ↩

9. 当 $p=5$ 时，Fibonacci 数列的特征方程 $x^2-x-1=0$ 有重根 $x=3$，因而在 ${\mathbf{F}}_5$ 中，Fibonacci 数列的通项公式是 $f(n)=n{3}^{n-1}$。 ↩

10. 所谓的环上的扩张，通常有两种含义：一种是 群的扩张的推广，一种是 域的扩张的推广。本文指的是第二种含义。更具体地说，本节涉及的扩张都是交换幺环上的 整扩张，它是域上的代数扩张的概念在交换幺环上的推广。 ↩