我们都知道3除以2等于1.5，但当我告诉你3除以2可以等于5也可以等于7，并且这一套体系是良好的时候，你一定很惊讶吧。
我们在生活中所运用的基本上是实数域内的运算，以至于我们考虑某一个问题的时候会自然而然的在实数域中去考虑它。但对于编码和计算机来说，每个比特能取到的值都是不连续的、都是有限的，甚至只能取0和1。所以我们需要给它们额外的一套体系——有限域。当然有限域本身也是很有趣的，例如它的四则运算、它独有的生成元、它的线性空间、······。
2019.6.22发布第一版，2022.3.19更新第二版。
群环域的概念
为了搞清楚什么是域，我们需要从集合说起。
集合(Set)
集合的概念就不用说了吧。集合具有三个性质：
无序性。集合中的元素是无序的。
唯一性。集合中的每一个元素都是唯一、不重复的。
确定性。给定一个元素和一个集合，这个元素要么在这个集合中，要么不在这个集合中。
然而朴素集合论是有缺陷的，大家可以搜索“第三次数学危机”、“罗素悖论”、“理发师悖论”、“哥德尔不完备定理”、“自我指涉”等关键词。现在我们使用的是ZF公理系统，它只是避开了这些缺陷而没有真正的解决这些问题，这里不深究下去了。
半群(Semigroup)
在一个集合S中定义一种运算(记作加法“+”，这个运算是人为定义的一个运算，只不过名字叫做“加法”，不一定就是我们生活中使用的加法)，并且这个加法运算需要满足以下性质：
封闭性。集合中的任意元素与任意元素做加法运算，结果还是这个集合中的某一元素。
结合律。也就是满足：(a+b)+c=a+(b+c)。
那么这个加法运算和这个集合S耦合的这么一个体系就是一个半群，记作(S,+)。例如在(0,1)这个开区间上定义加法运算为两个数的最大值，这就构成一个半群，但它不构成下述的幺半群。
幺半群
如果一个半群(S,+)中存在一个元素e，使得对于S中任意元素a都满足：a+e=e+a=a。那么这个半群就是一个幺半群，元素e被称为单位元或者幺元。例如在[0,1)这个左闭右开区间上定义加法运算为两个数的最大值，这就构成一个幺半群，单位元是0，但它不构成下述的群。
群(Group)
如果一个幺半群(S,+)中的任意元素a都对应着唯一的一个元素b且满足：a+b=b+a=e,其中e是单位元。那么这个幺半群就是一个群。元素a和元素b互为彼此的逆元，记作a=-b或b=-a。逆元的存在也就定义了群上的“减法”运算，a减去b其实就是a加上b的逆元：a-b=a+(-b)。要找一个是群但不是交换群的例子，多半来自变换群，例如在{“乘1”,“乘i”,“乘-1”,“乘-i”,"取共轭","先乘-1再取共轭","先乘i再取共轭","先取共轭再乘i"}这8个对复数作的变换构成的集合上，定义加法运算为变换的复合，那么这构成一个群，但不构成一个交换群。
交换群(Abelian Group)
如果一个群(S,+)满足交换律，即对于S中任意元素a,b，满足a+b=b+a。那么这个群被称为交换群。例如在{2^x:x∈ℤ}上定义加法运算为普通乘法，这构成一个交换群。
环(Ring)
在一个交换群上再定义一个运算(记作乘法“·”，同样，这个运算只是名字叫做乘法，与我们生活中使用的乘法无关)，得到(S,+,·)，并且满足：
(S,·)是一个幺半群。
分配律。即a·(b+c)=a·b+a·c。
那么(S,+,·)构成一个环，此时群(S,+)的单位元被称为环(S,+,·)的零元。
除环
如果幺半群(S,·)里出了零元以外的所有元素都有逆元，那么环(S,+,·)被称为除环。
为了防止与(S,+)里的逆元混淆，(S,+)里的逆元叫做加法逆元，(S,·)里的逆元叫做乘法逆元。与加法逆元一样，乘法逆元定义了“除法”运算，a除以b其实就是a乘以b的乘法逆元。
交换环
如果在环(S,+,·)中，乘法运算满足交换律，那么这个环被称为交换环。例如整数环ℤ，请注意它不是一个除环，从而它不是一个域。
域(Field)
如果一个环(S,+,·)既是除环又是交换环，那么这个环就是一个域。例如有理数域ℚ、实数域ℝ、复数域ℂ。
有限域GF(p)
有限域又叫伽罗瓦域(Galois field)，记作GF(p)，其中p是质数(后面讲为什么p一定是质数)。与我们生活中使用的实数域不同的是，有限域中的元素是有限的，每个有限域GF(p)中都会有p个元素，分别是0到p-1，例如GF(7)：{0,1,2,3,4,5,6}。
GF(p)中的四则运算
GF(p)中的四则运算都是基于取模运算的，那么什么是取模运算呢？它其实就是我们小学学过的带余除法的余数，例如：12除以7商为1，余数为5，记作12 mod 7=5，取模运算将不会考虑商而仅仅去考虑余数。如果两个不同的数a,b除以同一个数p之后余数相同，我们就称a,b模p同余，记作a mod p=b mod p。为了简便，我们会把“mod p”统一写到最后面，并且为了防止与“a=b”混淆，我们会使用恒等号“≡”，即a≡b(mod p)。例如12≡26(mod 7)。
GF(p)中的加、减、乘法都比较简单并且类似，所以放在一起讲。它们其实就是我们生活使用的加、减、乘法再取模p。例如在GF(907)中876+567≡536(mod 907)、234-345≡796(mod 907)、456·135≡791(mod 907)。
但GF(p)中的除法就有很大差别了，就像开头所说的有限域的运算是不会涉及到小数的，那么GF(p)的除法就要从乘法逆元出发了。毫无疑问GF(p)的单位元是1，因为任何元素乘1都等于它本身，所以一个数a的乘法逆元b应该满足a乘b等于1，即a·b≡1(mod p)。所以数c除以数a也就是数c乘以数b，设这个结果等于数x，那么a·x≡a·c·b≡c(mod p)(一个同余式的等号两边乘上一个与模互质的数时，等号仍然成立。我们这里的模p是一个质数，所以只要不乘p的倍数就行了)。这也就是说，我们要计算数c除以数a的结果数x，等价于我们要找到一个数x使得它满足：a·x≡c(mod p)。例如：在GF(19)中3除以2等于11，2除以3等于7。
现在我们可以来证明为什么p一定要是质数了。
证明：在有限域GF(a)：{0,1,···,a-1}中，若a不是质数，根据算术基本定理，数a一定存在一个以上的质因数，设其中一个为p且a=p·q，显然p<a。所以p是GF(a)中的元素，下面证明p没有乘法逆元：假设p有乘法逆元x，那么有p·x≡1(mod a)，即一定存在一个整数m(商)满足：p·x=m·a+1=p·m·q+1。所以p·(x-m·q)=1，即x-m·q=1/p，显然等式左边一定是一个整数，而等式右边一定不是一个整数，矛盾，故命题得证。
这里再说以下GF(p)中的幂。GF(p)中的幂其实就是多次累乘，例如在GF(17)中，3的8次方等于16。那么我们自然会想，既然有幂运算应该也有开方运算吧，很遗憾的是，有限域中没有开方运算。这是因为对于有些数，找不到一个数它的某次方等于这个数；而对于有些数，又能找到多个数它的某次方等于这个数。例如在GF(3)中没有数等于2开二次方根，而1开二次方根既等于1又等于2。
GF(p)的生成元(Generator)
生成元的概念其实在循环群中就出现了，我们这里直接讨论有限域的生成元。若有限域中某一个元素g，对于有限域中的任意一个非零元素b满足：b等于g的某次方，那么这个元素g就叫做有限域GF(p)的生成元。这里要指出的是，任意有限域GF(p)都存在生成元，证明过程蛮长的，感兴趣的同学可以去查找《初等数论》中“原根”的相关章节，这里不证明了。
我们再提一个定理——Euler定理(Euler定理其实有很多个，不然怎么叫欧拉大神呢)。
Euler定理 设m是大于1的整数，(a,m)=1，则
其中(a,m)表示a与m的最大公约数，φ(m)表示小于m的且与m互质的所有数的个数，证明过程不再给出。我们这里的m是质数p，a是有限域GF(p)中的非零元素，所以一定满足(a,m)=1，且φ(m)=p-1。也就是说在我们的有限域GF(p)中，对于某个生成元g来说一定有
所以序列
是以序列
为周期的，而序列S可以表示完GF(p)中的所有p-1个非零元素，所以S0也能表示完所有p-1个非零元素。恰好S0中有p-1个元素，所以序列S0会与有限域GF(p)中的所有非零元素一一对应(显然g^s≠g^t(mod p)，其中0≤s,t≤p-2，s≠t)。这也就是说，我们有了一种新的表示有限域GF(p)的方式，即
在使用新的表示方式之前，我们先来看看几个与生成元有关的命题。
命题1 除有限域GF(2)之外，任意有限域GF(p)的生成元都不会是1，也就是说至少是2。
命题2 任意完全平方数(1²,2²,3²,···)都不会是任意有限域GF(p)(p>2)的生成元。
证明：由于p是大于2的质数，所以p-1一定是一个偶数，根据Euler定理有
所以以完全平方数生成的周期序列S0的元素个数只有(p-1)/2个，这显然不能作为一个生成元。
命题3 更一般的，根据算术基本定理，p-1可分解为一些质数的乘积，即
那么对于任意的1≤i≤s，a^pi(a为正整数)都不会是GF(p)的生成元。
这里列出一些p-1与其对应的质因数，第一排为p-1，第二排为其对应的质因数。
貌似没有什么规律，可能要等黎曼猜想解决吧(个人认为)。
生成元的应用
有了生成元的概念，有限域GF(p)中的乘、除法就变的简单得多了，特别是除法。以下均不考虑零元。我们首先要证明的是在GF(p)中，有
其中m,n为整数。我们只需要证明若g^m≡s(mod p)，g^n≡t(mod p)则g^m·g^n≡s·t(mod p)，以上命题也就证明了。这是显然的，由于(g^n,p)=1，所以g^m·g^n≡s·g^n≡s·t(mod p)。这样我们就有了以下命题。
命题4 有限域GF(p)中的非零元素之间的乘、除法可转化为有限交换环{0,1,···,p-2}中的加、减法。
证明：这里直接证明除法。假设我们要计算s除以t，s,t为GF(p)中的非零元素。设g为GF(p)的生成元，r为t的乘法逆元，并且s≡g^m(mod p)，t≡g^n(mod p)，r≡g^q(mod p)，其中m,n,q均为有限交换环{0,1,···,p-2}中的元素。于是
所以n+q=p-1，即q=p-1-n。故g^(p-1-n)就是t的乘法逆元，s除以t也就是s乘以t的乘法逆元，那么
根据Euler定理有
故
现在总结一下，要计算非零元素s除以t：
先将s与t转换为生成元g的幂次m与n。
计算(m-n)mod (p-1)=x。
再将生成元g的幂次x转换为r，r即为s除以t的结果。
你可能会说，这没有变简单啊，难道这两次转换过程我不用算的吗。嗯，你真的不用算，因为我们可以制作一张表，这张表包含着有限域GF(p)中所有1到p-1的非零元素与有限交换环{0,1,···,p-2}中所有元素是如何一一对应的信息，我们每次需要转换的时候只需要查找这张表就可以了。当然这张反映对应关系的表是与生成元g有关的，它会随着生成元g的变化而变化，但我们在乘、除法运算过程中并不需要知道生成元g具体是哪一个，只需要保证整个运算中使用的生成元g统一就行了。
我这里列出一些有限域GF(p)的所有生成元，看似也没有什么规律。
GF(3):2
GF(5):2,3
GF(7):3,5
GF(11):2,6,7,8
GF(13):2,6,7,11
GF(17):3,5,6,7,10,11,12,14
GF(19):2,3,10,13,14,15
···
这里再列出有限域GF(13)的表，第一排是有限交换环中的元素，也就是生成元g的幂次，下面几排是特定生成元g的幂次对应的有限域GF(13)中的元素。第一排的生成元是2；第二排的生成元是6；第三排的生成元是7；第四排的生成元是11(其实表的第二列就可以看出使用的生成元是什么了)。
GF(p)中的数学
在GF(p)中会有很多有趣的现象，例如在GF(199)中直线2·x+3·y≡1(mod 199)的图像
二次函数y≡x²(mod 199)的图像
有趣的是虽然它的样子已经很不相同了，但它依然具有对称轴x=199/2。
三次函数y≡x³(mod 199)的图像
类似的，它也依然具有对称中心(199/2,199/2)。
自然的，我们想到了在GF(p)中圆的图像，但不能利用到圆心的距离为定值的定义来求，这是因为有限域里没有开方运算，除非额外定义“距离”。所以我们只能利用圆的方程来找出圆的图像，圆x²+y²≡2(mod 199)的图像为
看完了函数与方程(其他函数后面再说)部分，我们再来看看数列部分。
在GF(p)中等差数列还是蛮简单的，给定首项a1与非零公差d，其通项公式为an≡a1+(n-1)d(mod p)。很容易证明第p+1项与第1项是一样的，并且前p项两两互异。这也就是说GF(p)中的等差数列{an}都是以前p项为周期的，并且前p项恰好就是GF(p)中的p个不同的元素。那么等差数列{an}的前p项和Sp也就是0+1+···+(p-1)≡(p-1)·p/2(mod p)，由于(p-1)/2是一个整数，所以Sp≡0(mod p)，故等差数列{an}的前n项和就是
在GF(p)中等比数列就稍微有点复杂了，给定非零首项a1与非零公比q(且q≠1)，其通项公式为an≡a1·q^(n-1)(mod p)，由于涉及到了乘法运算，我们将其转化为生成元的幂次进行讨论。设g为GF(p)的某一生成元，a1≡g^b1(mod p)，q≡g^r(mod p)。那么通项公式为
令数列{bn}为bn≡b1+(n-1)r(mod p-1)，这样我们就将有限域GF(p)上的等比数列{an}转化为了有限交换环{0,1,···,p-2}上的等差数列{bn}。很容易证明前p项一定是等差数列{bn}的周期，但不一定是最小周期，这是因为r与p-1有可能不互质，通俗地说就是r帮n-1承担了一部分。这时等差数列{bn}的第(p-1)/(p-1,r)+1项与首项是相等的，即等比数列{an}以前(p-1)/(p-1,r)项为周期，并且很容易证明前(p-1)/(p-1,r)项两两互异。
这里我们会发现r是变动的，它会跟着生成元g的变化而变化；但是等比数列{an}是不变的，它不会随着生成元g的选取而变化，所以(p-1,r)也就应该是不变的。这样我们顺带地证明了下面这个命题：
命题5 设g1,g2,···,gs为有限域GF(p)的全体生成元，对于GF(p)中的任意非零元素x，它可表示为
其中a1,a2,···,as为有限交换环{0,1,···,p-2}中的元素，则a1,a2,···,as满足
利用错位相减法，我们可以得到关于等比数列{an}前n项和Sn的一个式子：(q-1)·Sn≡a1·(q^n-1)(mod p)。根据Euler定理，当n=p-1时，Sn≡0(mod p)，而前p-1项正好是周期(p-1)/(p-1,r)的整数倍。所以前(p-1)/(p-1,r)项和模p等于零，那么
我们再来看看其他部分。有限域中的元素不能比较大小，因为不满足：给定a,b,c，若a<b，则a+c<b+c。所以有限域中的数学没有不等式，函数也没有单调性可言，一切需要比较大小的数学都没有。有限域中的数学没有角度的概念，也就没有大部分的几何学，更没有三角函数。你可以试着利用麦克劳林展开计算sin(1)，但没有用，因为级数根本就不收敛，甚至连收敛的概念都没有，以至于与微积分和极限相关的绝大部分理论都没有。但好在线性代数还在，并且没有什么太大的变化，线性无关、矩阵的逆、特征值等都与我们所学的差不多，matrix67的这篇文章https://www.matrix67.com/blog/archives/4750就是一个应用有限域上线性代数的典例，题目是“选出最多的大小为奇数的子集，使得两两的交集大小都是偶数”。其他的留给大家去探索。
有限域GF(p^n)
在很多情况下，GF(p)是不够用的，比如在图像处理中，像素的色彩空间一般为RGB(红绿蓝)色彩空间，每种颜色的取值范围都是0~255。那么我们就需要另外一种有限域，它应该有2^8个元素。可是如果我们仍然用之前的加法运算与乘法运算的话，这是不能构成一个域的，所以我们需要引进新的加法运算与乘法运算。
GF(p^n)的运算用到了GF(p)的多项式的运算，我们先来看看一些关于多项式的概念。
如果在给定的一个域中，一个n(n>0)次多项式不能分解为两个或更多个多项式的乘积(这些多项式次数大于零，即不是常数)，那么这个n次多项式称为不可约多项式或者素多项式。例如在GF(2)中x³+x+1就是一个不可约多项式。
GF(p)中多项式的加、减、乘法就是我们生活中使用的多项式的加、减、乘法得到的结果多项式的各个系数取模p，例如在GF(2)中计算x³+x+1乘以x²+1：(x³+x+1)·(x²+1)≡x⁵+2x³+x²+x+1≡x⁵+x²+x+1(mod 2)。唯独除法略有不同，因为对于不可约多项式来说它没有除法，所以我们这里考虑的是带余除法，即a≡q·b+r(mod p)。这里a,b,q,r都是多项式，并且r的次数小于b的次数。但好在我们只需要考虑余多项式r，可以用辗转相除法求得，记为r=a mod b。例如在GF(19)中，8x³+4x²+7 mod 14x²+7x+12=4x+7。
GF(p^n)中的四则运算
在有限域GF(p^n)中，会事先选取一个次数为n的在GF(p)上不可约的多项式作为这个GF(p^n)的本原多项式。并且将GF(p^n)中的元素转换为p进制数，例如GF(2^4)中的11就是1011，GF(3^3)中的17就是122。这些p进制数分别对应着唯一的一个多项式，例如1011对应x³+x+1，122对应x²+2x+2。那么GF(p^n)中的任意元素都会与多项式有一个一一对应的关系。
GF(p^n)中的两个元素的加法运算的结果就是，在GF(p)中这两个元素对应的多项式相加的结果再去模事先选定的本原多项式，得到的余多项式对应的GF(p^n)中的元素。减、乘、除法类似。这里给几个例子：
在GF(2^3)中计算7+3与3-7，7与3的2进制数为111与11对应x²+x+1与x+1，(x²+x+1)+(x+1)≡x²+2x+2≡x²(mod 2)、(x+1)-(x²+x+1)≡-x²≡x²(mod 2)，x²对应2进制数100即4（加减法不需要本原多项式，因为不可能弄出高于n次的多项式）。故在GF(2^3)中7+3=4、3-7=4。
在GF(3^2)中计算4·8，4与8的3进制数为11与22对应x+1与2x+2，(x+1)·(2x+2)≡2x²+3x+2≡2x²+2(mod 3)，若选取x²+x+2为本原多项式，2x²+2 mod x²+x+2=x+1，x+1对应11即4。故在GF(3^2)中4·8=4。
在GF(5^2)中计算12除以13，我们先假设12除以13等于a，那么13·a=12，也就是说我们要找到一个数a使得13·a=12。13与12的5进制为23与22对应2x+3与2x+2，设a对应多项式b。若选取x²+2为本原多项式，那么我们要找一个多项式b使得(2x+3)·b mod x²+2=2x+2，像之前一样除法是比较麻烦的，不过我还是找到了，b是x+2、a是7。故在GF(5^2)中12除以13等于7。
GF(p^n)的生成元
因为GF(p^n)中的四则运算比较麻烦，所以研究起来也比较困难，后面的一些结论都是正确的，但是我没有能力去证明它们。所以大部分论文讲的有限域都是指GF(p^n)，感兴趣的同学可以去查找相关资料。
首先要说的是，有限域GF(p^n)是一定存在生成元的，并且生成元会随着选取的本原多项式的变化而变化。生成元的概念与GF(p)的一模一样，生成元g的0到p^n-2次幂一一对应着GF(p^n)中的p^n-1个非零元素，幂依旧是累乘的概念，只不过这里的乘法运算与GF(p)中的乘法运算不同，变得更复杂了。
有了这个结论，那么类似的，GF(p^n)依然可以表示为
并且依然满足
所以GF(p^n)中的乘、除法依然可以转化为有限交换环{0,1,···,p^n-2}中的加、减法。即GF(p^n)中的乘、除法依然可以用之前一模一样的查表法，只不过这里的表变了。并且同样的，与生成元的选取无关，但与本原多项式的选取有关，因为GF(p^n)的乘法运算法则是基于所选取的本原多项式的。
这里列出GF(5^2)的一部分可选取的本原多项式及其对应的所有生成元与其对应的表格。第一排是本原多项式，[1,0,2]表示x²+2，以此类推；第二排是相对应的所有生成元；第三排是对应生成元的表格，这里就不展示了。
有限域的应用
密码编码学
关于有限域在编码学上的应用这里不仔细展开了，感兴趣的可以搜一搜AES加密算法、RSA公开密钥体制，看一看这篇讲“离散对数和椭圆加密原理”的文章https://blog.csdn.net/qmickecs/article/details/76585303，如果后面密钥部分没看懂的还可以再看一看这个视频BV1ks41127LS。
快速数论变换(NTT)
快速数论变换可以视为快速傅里叶变换(FFT)的z变换版本，更多详情参见https://zhuanlan.zhihu.com/p/347726949。
扑克牌魔术？
扑克牌是魔术表演中十分经典的道具之一，而一副扑克牌有54张牌，去掉大小王有52张牌，每种花色又各有13张牌。注意到53和13均为质数，那么是否能从有限域的角度出发来设计一个扑克牌魔术呢？
参考文献
1.《有限域GF(2^8)的四则运算及拉格朗日插值》,https://blog.csdn.net/luotuo44/article/details/41645597
2.《谈谈有限域那些事儿》,https://blog.csdn.net/qmickecs/article/details/77281602
