域论

引入

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

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

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

记号

在不引起歧义时，本文可能会省略掉环和域的乘法记号，并且会将环写作环，将域写作域。环和域的加法单位元称为零元，乘法单位元称为幺元。而且，本文中的总是素数，而总是素数幂，且可以写作，其中，是正整数。

域的扩张

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

子域

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

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

域同态

自域到域的环同态也称为自域到域的 域同态（field homomorphism）。

域同态对幺元的处理

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

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

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

域扩张

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

域扩张的记号

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

例子

复数域就是实数域的扩张，而实数域又是有理数域的扩张。

域扩张的次数

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

域扩张的次数

域扩张的次数（degree），是指将看作是域上线性空间时的维度，即，记作。如果域扩张的次数是有限的，就称域扩张为 有限扩张（finite extension），否则就称为 无限扩张（infinite extension）。

例子

域扩张的次数等于，所以是有限扩张。域扩张是无限扩张。

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

定理

设都是域，则它们之间的扩张次数满足。

证明

对于扩张次数是无限的情形，这是显然的；否则，如果是作为上线性空间的一组基，且是作为上线性空间的一组基，那么可以验证，是作为上线性空间的一组基。

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

域的特征

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

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

域的特征

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

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

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

当特征为时，同态是单的，整数环嵌入了域中。有理数域作为最小的包含整数环的域必然也可以嵌入域中，它就是域的素子域；
当特征为素数时，同态的像嵌入了域中。此时，已经是域，记作，它就是域的素子域。

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

定理

域的特征只能是或素数。特征为的域对应的素子域是，特征为素数的域对应的素子域是。

定理中的和也称为素域（prime field），即子域只有它自身的域。有限域必然是有限特征的，因为特征为的域至少包含子域。

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

定理

设的特征为，则有：

域的加法群中，所有非零元素的阶都是，即对所有都有；
「新手之梦」（freshman's dream），即对所有都有。进而，映射是上的单自同态，叫做 Frobenius 自同态（Frobenius endomorphism）。

证明

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

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

单扩张

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

由子集生成的域扩张

设是域扩张，，那么 由生成的域上的扩张（extension generated by over ）就是指同时包含和的，最小的的子域，记作。

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

有限生成扩张

设是域扩张，如果存在有限集使得成立，则称为域的 有限生成扩张（finitely generated extension），也记作。

单扩张

设是域扩张，如果存在使得成立，则称域是域的 单扩张（simple extension）。其中，元素称为这个单扩张的 本原元（primitive element）。

例子

这些例子都是向中添加中的元素得到的。

对于无平方因子的整数，二次域就是在域中添加了得到的单扩张。它的扩张次数是，因为构成了一组基。
域就是在域中添加了和得到的扩张。当然有，即最后的扩张与元素的添加顺序和方式无关。这也是单扩张，因为。它的扩张次数是，因为构成了一组基。
域也是单扩张，其中，是圆周率。它是无限扩张，因为已经有一组基。
域是有限生成的扩张，但不是单扩张。其中，是圆周率，是自然对数的底。

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

代数扩张

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

设环同态满足限制在上是恒等映射，且，即将不定元映射到扩张中的某个元素。此时，因为像必然是整环，同态的核必然是多项式环的素理想。域上的多项式环是主理想整环，因而它必然有的形式，其中或是中的不可约元。对此有如下讨论：

当同态的核时，多项式环嵌入到中，它的像是整环。因而，域中同时包含和的最小的域就是的分式域，即。这个记号，既可以解释为将有理分式域中的不定元代入的结果，也可以解释为域上由生成的单扩张：这两个解释在这个语境下得到的结果是一致的；
当同态的核，且为不可约元时，就成立，即是上的多项式的根。因为是域，不妨设是首一多项式。此时同态的像是域，故而有

此时又可以分为两种情形：
1. 如果是一次多项式，即时，有，故而扩张是平凡的；
2. 其余情形，是高于一次的不可约多项式，且，此时的像已经是包含和的域，因而，它就是，即上由生成的扩张，且不是平凡的。

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

代数元与超越元

对于扩张，如果元素是上某个非零多项式的根，则称是上的 代数元（algebraic element）；否则，称元素是上的 超越元（transcendental element）。

极小多项式

对于域上的代数元，以为根且次数最小的首一多项式称作它的 极小多项式（minimal polynomial）。

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

例子

是上的代数元，极小多项式是。
是上的代数元，极小多项式是。
是上的超越元。
一般地，上的代数元称为 代数数（algebraic number），而超越元称为 超越数（transcendental number）。特别地，如果代数数的极小多项式是首一多项式，它就称作 代数整数（algebraic integer）。代数扩张中的全体代数整数构成环。例如，二次域中的代数整数就构成二次整数环。此处记号的含义见二次整数环页面。

代数扩张与超越扩张

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

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

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

定理

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

证明

设为域，为域上的有限生成代数扩张，即都是上的代数元。设，则且。注意到，必然是上的代数元，因为在域上的极小多项式也是上的多项式；而且在上的极小多项式次数必然不超过在域上的极小多项式次数。故而，必然是有限的，根据域扩张次数的乘法原理，也是有限的。反过来，从开始，对于已经构造好的，可以每次都在中选择元素加入到中，得到扩域，直到为止。因为扩张的次数在不断的降低，这个过程必然在有限步内终止。因此，有限扩张必然是有限生成的代数扩张。

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

单代数扩张的结构与计算

本节中，设是数域，是它的扩域，且是域上的代数元。设的极小多项式是，且多项式是次首一多项式，亦即

其中，且在上不可约。

同构关系指出，扩域中的运算就是模的多项式的计算。根据多项式的带余除法，只需要考虑所有次数小于的多项式的同余类就可以了。对于这些多项式，自然的一组基就是。因此，有如下结论：

定理

在本节的假设下，扩域可以写作

其中，遍历全体次数小于的多项式。因此，扩张次数，即的极小多项式的次数。扩域中，元素和的加法，就是多项式的加法，即对应位置的系数相加；元素和的乘法，结果可以写作，其中是乘积除以的余式。

当然，作为域，还可以计算中元素的除法。根据定理中描述的乘法的过程，这相当于求解多项式环上的线性同余方程。类比整数的做法，要计算商，可以先确定的乘法逆元，再乘以即可。要计算的乘法逆元，只要解同余方程即可。这可以通过扩展欧几里得算法实现。

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

例子

考察扩域，其中的是方程的一个根。要计算

的值。

第一步是计算的逆元，也就是要计算同余方程

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

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

因而，方程的解为

这说明的逆元是

第二步，就是计算逆元和的乘积。对此，有

这就是最后的答案。

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

一般地，对于域上的不可约多项式，在扩域中有不同的根，这些根在分别对域做单扩张时表现出相同的代数性质，这些根互相称为共轭（conjugate）。复数域上的通常意义的共轭，就是这一概念在域扩张上的特例。

例子

考察扩域，其中的是方程的一个根。一般地，对于和，有运算规则

这提供了类似于复数域上的运算法则。大多数读者对于这样的根都应当是陌生的，但这并不妨碍对这样的域中的元素进行运算。实际上，有，因而，作为线性空间，即这样得到的是大小为的有限域。稍后会看到，所有的有限域都是这样构造的。

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

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

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

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

分裂域

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

例子

考察扩张。代数元在域上的极小多项式是。在复数域中，多项式有三个根，即，其中，是的三次原根。尽管，但是中并没有另外的两个根，这使得这种运算就已经无法进行。如果要完整地考察这三个根，需要对域做进一步扩张，即扩张至。

前文已经说明，要做这样的扩张，只要对元素逐个做单扩张即可。应当注意的是，在域中和在域中的极小多项式并不相同：前者是，后者则是，因为有

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

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

分裂

设为域。如果多项式在中可以分解为一系列一次因子的乘积，就称多项式在域中分裂（split）。

分裂域

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

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

正规扩张

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

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

代数闭域

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

代数闭包

对于域，如果域是域的代数扩张，且所有的都在中分裂，则称域是域的 代数闭包（algebraic closure）。

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

定理

任何域都有代数闭包。

证明

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

证明的第一部分从出发，构造了扩张使得所有上的多项式在中都有至少一个根。对于域，考察多元多项式环⁴ ，其中的不定元的下标取遍所有上的首一多项式。此时，由所有生成的理想记作。首先，，故而极大理想存在。否则，如果，必然存在有限多个域上的首一多项式和相应的环中的元素使得成立。设为向中添加的根后得到的代数扩张，则在中令上面得到的恒等式中都代入，而在各个中出现的其它不定元都带入，则得到上的等式，这矛盾。故而，，极大理想的构造是合法的。此时商环是域，记作，且任何上的首一多项式都在中有根。

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

最后，令中所有上的代数元组成的集合记作。它显然是域；因为对于任何，都有。它也是的代数扩张，因为它的元素都是上的代数元。对于上的多项式，它的所有根都是上的代数元，故而也在中，故而必然可以分裂为一次因子的乘积。这就说明是上的代数闭包。

例子

实数域的代数闭包是复数域。
有理数域的代数闭包是全体代数数（即域扩张中的代数元）的集合，记作。

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

代数闭域

如果域上任意多项式都至少有一个根，那么就称域为一个 代数闭域（algebraically closed field）。

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

定理

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

域是代数闭域；
域上的所有多项式都分裂；
域上的不可约多项式只有一次多项式；
域没有非平凡的代数扩张；
域没有非平凡的有限扩张；
域是某个域的代数闭包。

证明

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

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

可分扩张

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

可分多项式

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

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

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

形式导数

域上的多项式

的 （形式）导数（derivative），记作，定义为多项式

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

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

定理

对于域上的多项式，如果有重根，那么导数也有同样的根。进而，多项式可分的充分必要条件是与它的导数互素，即。

证明

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

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

对于域上的不可约多项式，多项式作为的因子，只能有两种情形，即或者。对于前一种情况，多项式自然是可分的；问题出现在后一种情况。但是，由于导数的定义中已经保证或者，多项式成为的因子，只能说明。这在有限特征的域中是有可能的。

对于特征为的域，如果，则多项式的所有非零系数都只能出现在次数恰为的倍数的项上，即多项式可以写作

如果真的存在域上的多项式既不可约也不可分，则它只能有这种形式。但是，如果域中的所有元素总有次根，即对每个系数都存在使得可以写作的形式，那么，根据 Frobenius 自同态，总有

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

完美域

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

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

定理

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

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

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

定理

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

有理数域和下文会讨论的有限域都是完美域。

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

例子

考虑的有理分式域上的多项式。因为是唯一分解整环的分式域，且是中的素元，则对素元应用 Eisenstein 判别法可知在中不可约，故而在中也不可约。但是，它的导数为，因而并不可分。事实上，在扩域中，它有二重根。

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

可分扩张

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

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

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

分圆域

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

单位根群

复数域中，多项式的根称为 次单位根（-th root of unity）。记。那么，全体次单位根就是集合。在乘法运算下，构成次循环群，可以记作，称为次单位根群。群的生成元，也就是那些阶恰好为的元素，称为 次本原单位根（primitive -th root of unity）。次本原单位根的集合，恰有个元素；其中，是欧拉函数。将单位根群的元素按照它的阶分类，就得到如下分解：

对两边元素计数，就得到恒等式。

分圆域

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

分圆域

将次复单位根添加到有理数域中得到的扩域称为 次分圆域（-th cyclotomic field）。

因为全体次单位根在乘法运算下构成循环群，分圆域也包括所有这些次单位根。其实，正是域上多项式的分裂域。

定理

分圆域是有理数域上多项式的分裂域。

证明

设为有理数域上多项式的分裂域。因为上有多项式的全体复根，所以。反过来，因为，就必然有。这就说明。

这可以作为分圆域的等价定义。其实，将任何次本原单位根添加到分圆域中都能够得到。

分圆多项式

分圆域是有理数域上的单代数扩张。根据上文的分析，这样的域总是同构于某个多项式环的商环。为了得到这样的同构，需要分析的极小多项式。因为是的根，所以必然是的某个因子。这说明，需要考察多项式在内的因式分解。根据 Gauss 引理，它必然可以在中分解为若干个不可约的首一多项式的乘积。

因为是分裂域，多项式有分解：

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

即可。单位根的极小多项式，必然是的因子。而且，这样定义的有如下性质：

定理

是整系数首一多项式，且在中不可约。

证明

由定义，显然是首一多项式。首先，要证明。根据 Gauss 引理，多项式在和中有着相同的分解，且每个因子都是整系数首一多项式。这个分解中，每个因子都是上不可约的，且在中分裂；它的所有根都是次单位根，且必然有着相同的阶，所以这些根必然全部属于某一个而不能分别存在于不同的。这意味着，每个因子都是某个的因子。故而，可以写成若干个的整系数首一多项式的乘积，必然也是整系数首一多项式。

接下来，要证明在是不可约的。设它有分解，且在中不可约，那么只要证明包含所有次本原单位根即可。也就是说，设是的一个根，要证明对于所有，都有也是的根；由于总是可以分解为素数的乘积，所以只需要证明对于所有素数，是的根就可以了。假设不然，是的根。因而，是中多项式和的共同的根。因为是在上的极小多项式，必然有整除；亦即存在使得。等式两侧同时对取模，得到上的等式。利用 Frobenius 自同态可知，。因为也是唯一分解整环，和必然有不平凡的公因子，所以，在上不可分。但是，因为，它的形式导数与它自身互素，这与它不可分矛盾。故而，可以证明必然还是的根，因而包含所有次本原单位根，它就是。

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

分圆域中的代数整数环是。另外，当时，分圆域是二次扩张。具体来说，是二次域；和相同，都是二次域。

利用分圆多项式，多项式在中有唯一分解

因此，当且仅当。而且，对此式应用 Möbius 反演可得

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

分圆多项式

前个分圆多项式如下：

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

利用上文的 Möbius 反演式，可以总结出如下性质来简化的计算：

性质

对于分圆多项式，有：

如果素数，则；
如果素数，则；
特别地，如果是奇数，则；
对于素数，有；
特别地，。

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

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

定理

设为次分圆多项式，且多项式的次数是。于是，有：

多项式是回文多项式，它的次项系数和次项系数相同，即；
多项式的次项系数等于 Möbius 函数；
如果是素数幂，那么；否则，；
设且为的素因子，则，或者是乘法群中的的阶，且这两种情况不能同时发生。

证明

对于前三条性质，只需要利用 Möbius 反演即可。对于 1，直接考察的 Möbius 反演形式，即；对于 2，设的次项系数为，则比较等式两侧的次项系数可知，，再做 Möbius 反演；对于 3，在两侧同时除以，再代入，即有，再做 Möbius 反演。

下面证明第四条性质。首先，如果是乘法群中的的阶，那么是满足的正整数中最小的，故而。反过来，如果，则有；可如果不是乘法群中的的阶，那么设它的阶为，必然有且。此时，和在域中有公共根，这说明有重根。这说明；否则，与它的导数互素，所以在上可分，不可能有重根。因而，的素因子只有两种情况：，或者是乘法群中的的阶。这两种情况是互斥的，因为后者意味着。

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

有限域

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

定理

大小为的域存在，当且仅当具有素数幂的形式。而且，这样的域在同构意义下唯一，记作。素数是域的特征，正整数为域扩张的次数。最后，是上多项式的分裂域，且恰好包括的个互异的根。

证明

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

反过来，给定素数和它的幂，要说明上的多项式的分裂域恰好有个元素，才能说明所有素数幂阶的域都存在。因为上的多项式的分裂域总是存在，所以可以设该分裂域中多项式的全部根组成的集合为。现在要证明是域，因而它就是多项式的分裂域本身。但是，迭代次 Frobenius 自同态就可以知道也是自同态，因此对任意都有，和。因此，集合对加、减、乘、除都封闭，它是域。这就说明就是上的多项式的分裂域。

推论

有限域（）中，全体非零元的和是，积是。

证明

有限域的全体非零元恰好是多项式的个根，应用 Vieta 定理即可。

在素域中，这个推论关于积的结论正是数论中的 Wilson 定理（的一部分）。

乘法结构

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

定理

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

证明

设为域的乘法群的子群且。因而，是有限 Abel 群。根据有限 Abel 群基本定理，群有不变因子分解且。所以，对于中的所有元素，都有。也就是说，群中的元素都是域上多项式的根。但是，多项式至多有个相异的根，即。但是，，所以其实有。这说明，即群是循环群。

推论

有限域的乘法群。

循环群中有个生成元，它们称为有限域的本原元；其中，是欧拉函数。

本原元

有限域的乘法群的生成元，称为的 本原元（primitive element）。

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

尽管单扩张中的本原元和有限域中的本原元的名称一致，两者并不相同。单扩张中的本原元是相应的单扩张的生成元，而有限域中的本原元是相应的乘法群（作为循环群）的生成元。有限域作为它的素子域的单扩张的本原元，未必是有限域本身的本原元。例如，中，是域扩张的本原元，但是并不是域的本原元，因为它的阶数是。

中的本原元和模

的原根也不相同

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

设是有限域的一个本原元。那么，对于所有都存在唯一的自然数使得；这个就称为上元素关于基的 离散对数（discrete logarithm）。和上的情形一致，离散对数的算法的复杂度都比较高。

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

定理

对于有限域，设为的子域，则是上的单代数扩张；又设为的本原元，则。

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

包含关系

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

定理

设和是有限域，则是的子域，当且仅当存在使得。换句话说，是的子域，当且仅当。

证明

如果是的子域，那么两者必然有相同的特征。域扩张、和都是单代数扩张，分别记它们的扩张次数为，则扩张次数必然满足。而且，和，并成立。

反过来，要证明对于所有，都是的子域。记且。设为有限域中方程的全体根的集合。通过 Frobenius 自同态可以证明，集合必然构成域；关键是要证明，这样的根恰好有个，所以才有。因为，所以，所以，也就是。所以，在上分裂，故而在内有个不同的根。这就说明是的子域。

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

定理

设为的代数闭包，则域中多项式的根的集合构成有限域。那么，有：

，即的代数闭包就是所有特征为的有限域的并集；
全体特征为的有限域在包含关系下形成的格，同构于整数在整除关系下形成的格。特别地，和的交集，而同时包含和的最小的域。

证明

关键在于证明第一部分，即是的代数闭包。第二部分是前面关于有限域的子域的定理的简单推论。

注意到，任取，必然存在使得成立，故而是上的代数元；因而，是的代数扩张。对于任何上的次多项式，它在代数闭包中有至多个不同的根。设根的极小多项式次数为，则必然包含在域内；故而，的所有根都在中，亦即在上分裂。根据代数闭包的定义，就是的代数闭包。

自同构群

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

特征为的域上都有 Frobenius 自同态。对于有限域的情形，这也是自同构；这说明有限域都是完美域。域的自同构群就是阶循环群，它的一个生成元就是 Frobenius 自同态。

定理

有限域的自同构群是阶循环群，且生成元是 Frobenius 自同态。

证明

首先，Frobenius 自同态在有限域上是自同构，因为有限集合上的单射必然也是满射。因此，。

然后，的阶是。这是因为对于所有都有，故而是恒等映射；而且对于任何都有不是恒等映射，否则的元素都得是的根，这不可能。

最后，至多有个元素。设为的一个本原元，则自同构由它在处的取值唯一确定。但是，必须将映射到它的共轭元；否则，和不再是同一个极小多项式的根。这样的共轭元只有个，这就说明也至多有个元素。

因此，中的个元素正是。定理得证。

自同构群的子群和有限域上的子域一一对应。

定理

设为有限域，为它的全体子域，为它的自同构群的全体子群。对此，有：

对于，设为中保持不变的自同构的集合，即，则；
对于，设为中的所有自同构的不动点集合的交集，即，则为的子域；
映射和映射互为逆映射，且是和之间的一一对应；
这个一一对应，将子域之间的扩张关系映射为子群之间的包含关系，即对于任何，都有。

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

不可约多项式

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

有理数域上的代数元可以根据其极小多项式的次数分类。设是极小多项式次数恰为的代数元集合，则

这对应着因式分解

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

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

所以，上的次不可约首一多项式共计

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

定理

有限域上存在任意次数的不可约多项式。

因为有限域上的不可约多项式有着简单的结构，这使得有限域上的多项式的因式分解十分容易。比如，要确定给定多项式的全体次不可约因子，只要求解给定多项式与的最大公因子即可⁶。类似地，只要次多项式对所有的都与多项式互素，就可以断定该次多项式在上不可约。

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

定理

设为素数，为正整数，且。又设是乘法群中元素的阶。那么，分圆多项式在域可以分解为个上的次本原多项式的乘积。特别地，分圆多项式在域上不可约，当且仅当是模的原根。

证明

如果注意到，次分圆多项式的根是所有的次本原单位根，而次本原单位根的极小多项式的次数就是它的共轭（包括自身）的数量，也就等于它在自同构群下的轨道长度，那么就可以知道是中映射的循环子群的轨道长度，亦即乘法群中元素的阶。如果不想依赖于 Galois 理论，也可以通过说明是最小的正整数使得成立来证明此事。其余结论显然。

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

参考实现

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

参考实现

#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;
}

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

应用

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

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

斐波那契数列

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

现在要计算在素数模下的值⁹。将这个问题转化为有限域上的计算，首先要解决的就是在中的意义。从代数角度看，它就是元素的平方根。因而，如果中存在的平方根，即是模的二次剩余的时候，可以直接计算其二次剩余并带入计算；否则，就需要在扩域下进行计算。

当然，在扩域中进行计算的时候，没有必要一定加入。比如说，对于斐波那契数列，也可以设是多项式的根，从而可以写作

如果并非模下的二次剩余，多项式就是不可约的。此时，可以在扩域上进行计算，能够得到和前文一致的结果。

计算斐波那契数列的方法当然可以推广到别的情形。但是，有一点应当注意：有限域上多项式的不可约性和有理数域并不一致。譬如，它在上是不可约的，相应的分裂域是；但是在中，如果和都不是模的二次剩余，那么它是两个不可约多项式的乘积，亦即在扩域中就已经存在平方根而不需要进一步扩张。

推广到环上的「扩张」

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

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

的常数项即可。比对上文中的通项公式，这个做法的合理性是显然的：这似乎就是在「扩张」中计算

的值，且是的根。

虽然没有那么显然，但是这个做法也是合法的。注意到，在有理数域的扩张中，通项公式成立。这就说明，在中，

成立。这只涉及到整系数多项式，因而在中也成立。写成带余除法，等式两边的系数都对取模，就得到上的恒等式。这个结论对于任意都成立。

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

Cipolla 算法

这是利用有限域的扩域进行计算的典型例子。对于模下的二次剩余，要找到它的平方根，即使得成立的。虽然这是上的问题，但是 Cipolla 算法在有限域上进行计算。本节使用域论的语言对这个算法进行说明。初等数论的证明可以参考所给链接。

具体来说，Cipolla 算法首先选择使得是模的二次非剩余，这意味着是不可约多项式。因而，令，可以考虑扩域。因为 Frobenius 自同态只能将元素映射到它的共轭，而这样的共轭在二次扩张中是唯一的，即有。故而，。所以，要确定平方根，只要计算就好了。这个值必然位于中，因为的分裂域就是本身。

习题

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

分圆多项式：
- Luogu P1520 因式分解
- [FZU 2022 Team Training] Problem C. Call It What You Want
有限域：
域扩张：
- [Oleksandr Kulkov Contest 2] Problem A. Square Root Partitioning
- CF1103E. Radix Sum

参考资料与注释

Dummitt, D.S. and Foote, R.M. (2004) Abstract Algebra. 3^rd 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

这是因为域的幺元必然满足上的关系，而后者在域内只有两个根和，由于域的定义要求，就必然有和。 ↩
用范畴论的语言来说，就是是幺环范畴的始对象。 ↩
严格地说，这里指的是多项式环的万有性质（universal property）。 ↩
此处的多项式环有无限多个不定元。要定义这样的多项式环，首先要定义单项式。设不定元的集合为，则它上面的单项式是全体只在有限多个不定元处取值不为零的函数，可以记作，其中，是所有取值不为零的不定元的指标。多项式是所有有限多个单项式的线性组合。它们在相应定义的加法和乘法运算下成为环。对于有限多个不定元的情形，可以证明这种定义与多元多项式环一节的递归定义得到的结果是一致的。 ↩
虽然名字是代数基本定理，这个结论并不是纯代数的，这是因为实数域的构造需要通过拓扑结构进行。 ↩
这样的说法有失严谨，因为还会得到次数的不可约因子。但是，由于算法实现时通常会从较小的次数的因子开始分离，在分离次不可约多项式因子时，较小的因子应该已经分离完了，所以这说法也是可以接受的。 ↩
不要把这里的名称和多项式理论中的本原多项式（即所有系数的最大公因子是一的多项式）混淆。 ↩
比如，Hansen, T., & Mullen, G. L. (1992). Primitive polynomials over finite fields. Mathematics of computation, 59(200), 639-643 的附录就提供了这样的列表。 ↩
当时，Fibonacci 数列的特征方程有重根，因而在中，Fibonacci 数列的通项公式是。 ↩
所谓的环上的扩张，通常有两种含义：一种是群的扩张的推广，一种是域的扩张的推广。本文指的是第二种含义。更具体地说，本节涉及的扩张都是交换幺环上的整扩张，它是域上的代数扩张的概念在交换幺环上的推广。 ↩

最后更新: 2024年11月27日
创建日期: 2024年11月27日