type
status
date
slug
summary
tags
category
icon
password
有限域——多项式环的商环构造有限域
有限域，顾名思义就是有限的域，我们又称它为Galois域(Galois Field)。
环
说到域，首先得要讲讲环(ring)。
环中存在两种封闭的二元运算——加法和乘法。加法和乘法只是我们的称呼，以区别两种运算。环要满足以下条件：
1.环的所有元在加法上是一个交换群(Abelian Group)（满足结合律，交换律，存在e元，这里我们称之为0元，满足每个元都有唯一的逆元）。
2.环的所有元在乘法上是一个半群(即只要满足结合律)。
3.加法、乘法满足左分配律和右分配律。
我来举几个例子，比如所有的整数在加法、乘法下就是一个环。
再来个复杂的例子，所有的实数下的n阶方阵在矩阵加法和矩阵乘法下也是一个环，0元为n阶0方阵。注意，这里的乘法不可交换。
域
人类很早就认识到自然数，在慢慢历史长河中，加减法、乘法都是很早就产生。涉及到公平性问题，又带来了除法，于是引入了分数的概念。
但引入了除法之后，我们可以在整数环的基础上构造有理数域。
我们最常见的域有理数域就是在整数环的基础上引入除法得到的。
不是所有的环都可以扩展成一个域的，有些环天生不足，比如刚才提到的矩阵环，不仅仅因为矩阵乘法不可交换，而且里面充斥着两个非0元乘积等于0元的情况。
比如
这样的元叫零因子，没有零因子的环叫整环，比如整数环。当然整数环中有一个元素也很特殊，那就是1，1和任何整数的乘积还是那个整数本身，我们可以称呼环中满足这个性质的元叫1元。
实际上，我们对于含有1元的交换整环，按照我们构造有理数域的方法都是可以构造成域的，这叫分式域。
但我们构造Galois域的方法其实还是用的其他方法，这个以后再说。
域的所有非0元在乘法下也是一个交换群(Abelian Group)。
域有个重要的性质，就是特征，除0元之外的每个元的加法群周期都相同，这个周期称之为特征。当然，对于我们的有理数来说来说，这个周期是无穷。如果域的特征不为无穷，而为整数，实际上是可以证明其只能为质数(Prime Number),这里不讲如何证明。
域有子域的概念，某个域的其中一部分元在加法、乘法上还是一个域，则这一部分元所成的域为原来域的子域。用平常的例子，我们的有理数域其实是实数域的子域，而实数域则是复数域的子域。实际上，我们的实数域、复数域有无穷多个子域。
比如集合 {x|x=a*√2 + b, a和b是有理数} 在加法、乘法上就是一个域。
每个特征下都有一个独特的域，使得任何一个同样特征的域都有一个子域与之同构，则为素域，有理数域就是一个素域。
我们既然考虑有限域，那么针对的是特征为质数的域。
素域
实际上，特征为质数的素域是很容易构造的，假如说特征为p，素域的元素个数则为p，设为0,1...p-1
素域内的加法定义为模p加法，也就是
(a+b)%p
素域内的乘法定义为模p乘法，也就是
(a*b)%p
我们很容易证明这是一个交换环，而且存在1元。
对于除法，
a/b = a*bp-2
这里的乘法和幂用的都是模p乘法。
我们很容易写一个scheme程序来看一个特征p素域中所有的+-*/运算：
zero?这个运算有的scheme未必有，定义如下
(define zero? (lambda (x) (= 0 x)))
对于特征5的素域，我们运算一下所有的加减乘除：
运算，得到
0+0=0 0-0=0 0*0=0
0+1=1 0-1=4 0*1=0 0/1=0
0+2=2 0-2=3 0*2=0 0/2=0
0+3=3 0-3=2 0*3=0 0/3=0
0+4=4 0-4=1 0*4=0 0/4=0
1+0=1 1-0=1 1*0=0
1+1=2 1-1=0 1*1=1 1/1=1
1+2=3 1-2=4 1*2=2 1/2=3
1+3=4 1-3=3 1*3=3 1/3=2
1+4=0 1-4=2 1*4=4 1/4=4
2+0=2 2-0=2 2*0=0
2+1=3 2-1=1 2*1=2 2/1=2
2+2=4 2-2=0 2*2=4 2/2=1
2+3=0 2-3=4 2*3=1 2/3=4
2+4=1 2-4=3 2*4=3 2/4=3
3+0=3 3-0=3 3*0=0
3+1=4 3-1=2 3*1=3 3/1=3
3+2=0 3-2=1 3*2=1 3/2=4
3+3=1 3-3=0 3*3=4 3/3=1
3+4=2 3-4=4 3*4=2 3/4=2
4+0=4 4-0=4 4*0=0
4+1=0 4-1=3 4*1=4 4/1=4
4+2=1 4-2=2 4*2=3 4/2=2
4+3=2 4-3=1 4*3=2 4/3=3
4+4=3 4-4=0 4*4=1 4/4=1
子环
环的一个非空子集，如果在加法和乘法上依然是个环，那么就称这个环是原来的环的子环。
我们依旧举几个例子，比如：
对于有理数域（当然也是一个环），整数环就是它的一个子环；
对于整数环，所有偶数依然在加法、乘法下构成一个环（因为任何两个偶数通过加、减、乘得到的还是偶数，对于加、减、乘是封闭的，所以依然是一个环），这个偶数环是整数环的一个子环；
对于n阶实数矩阵环，其所有的非对角线上的值全为0的n阶矩阵在矩阵加法、矩阵乘法上也构成了原矩阵环的一个子环，很明显，对于a、b两个矩阵，如果非对角线上为0，那么无论加法、减法还是乘法，得到的结果非对角线上都为0。
理想
理想(ideal)是一种特殊的子环，在子环的基础上，理想还要满足如下条件：
如果B是A的一个理想，那么对于任何a∈A，b∈B，有ab∈B且ba∈B。
其中ab和ba是a,b顺序不同的乘法结果（乘法未必可以交换）。
理想要满足ab∈B和ba∈B。
另外引申两个概念：如果满足ab∈B，叫左理想；如果满足ba∈B，叫右理想。
很明显，每个环至少有两个理想：一个理想是单个0元所组成的环，因为任何一个元与0元的乘都为0元；另一个是这个环本身。
既然这两个理想对于每个环都有，不具有什么研究意义，我们称之为平凡理想。
只有非平凡的理想对于我们才有研究意义。
我们还是先以整数环举例，对于整数环，显然，所有偶数组成的子环是一个理想，因为任何整数和偶数的乘积还是偶数。
我们再去思考实数上的n阶矩阵环有没有非平凡理想：
实际上，假如该矩阵环中有一个理想，这个理想中存在一个秩为m(0<m<n)的方阵M，按照线性代数知识，存在X和Y两个满秩方阵，使得
XMY = Im 0mx(n-m)
0(n-m)xm 0(n-m)x(n-m)
I1 0 * Im 0 = I1 0
0 0 0 0 0 0
这里的I是单位方阵。
有了这个方阵，则可以通过行变换、列变换变换到任何只有一个元素不为0的方阵，
再通过加法，可以得到所有的n阶方阵。
从而该理想其实包含该环中所有方阵。
于是实数域上的矩阵环是不存在非平凡理想的。不存在非平凡理想的环叫单环。
其实实数域矩阵环是存在非平凡的左理想和右理想的：
比如第一行之外其他行全为0的方阵构成一个左理想，第一列之外其他行全为0的方阵构成一个右理想。
甚至，我们可以深入研究下去，从而可以搞清楚实数域矩阵环的所有的非平凡左理想和非平凡右理想，这里并不展开此问题。
再来看看域的理想：
对于任何一个域，因为域除了0元外，其他元在乘法上构成一个群，所以域的理想如果包含了任何一个非0元，那么必然扩充到整个域。从而，域没有平凡理想，所以也是单环。
生成元
抽象代数里，我们很多时候研究方法都是采用生成元的方法。
在这里，我们研究环的理想的方法也是采用生成元，上面的分析中其实已经蕴含了这样的思想。
我们说一个理想是用某几个元生成的（也就是说这几个元是该理想的生成元），意思是指包含了这几个元的最小理想。
我们之前提到所有偶数构成的环是整数环的理想，其实也可以看作是以2或-2为生成元的生成理想。
同理、以3、4、5、6.....各自为生成元，都可以产生整数环的一个非平凡理想。其实，利用数论里的知识也可以证明，整数环的任何非平凡理想都可以用一个元生成。
商环
有了环的理想，我们可以构造一个神奇的东西——商环。
我们先定义一下分划：
A的一个分划是指A的一个非空子集的集合，并且满足A上所有元素有且只在其中一个非空子集上。
比如{1,2,3,4}分划有：
{{1,2},{3,4}}，
{{1},{2},{3},{4}}，
{{1},{2,3,4}}...
也就是把一个集合“分成任意块”，分划内的任意一个元素（原集的一个非空子集),我们称之为类。
我们这样定义环R对于理想I的商环Q：
商环Q是R的一个分划；
R里任何两个元x和y，在Q的同一个类里的充要条件是x-y∈I；
商环上定义的加法为：商环里的两个类A和B，A+B的结果是A上的一个元素a和B上的一个元素b做加法得的a+b所在的类；
商环上定义的乘法为：商环里的两个类A和B，A+B的结果是A上的一个元素a和B上的一个元素b做乘法所得的ab所在的类。
我们来证明以上加法、乘法定义是合理的，换句话说，加法、乘法的唯一性，用数学语言来说如下：
对于任意Q内的A和B，对于任意a1,a2∈A, b1,b2∈B,存在一个Q内的C和D，使得
a1+b1∈C,
a2+b2∈C,
a1b1∈C,
a2b2∈C.
稍微转换一下，就是
a1-a2∈I /\ b1-b2∈I -> (a1+b1)-(a2+b2)∈I /\ a1b1 - a2b2 ∈I
证明起来不难，
(a1+b1)-(a2+b2) = (a1-a2)+(b1-b2)
a1-a2和b1-b2都在I里，两者的和当然也在I里。
我们假设a1-a2=i1, b1-b2=i2
当然，i1和i2都是I里的元，
a1b1 - a2b2 = (a2+i1)(b2+i2) - a2b2
= a2b2 + i1b2 + a2i2 + i1i2 - a2b2
= i1b2 + a2i2 + i1i2
因为I是理想，所以i1b2、a2i2、i1i2都在I里，所以三者的和叶在I里。
得证。
唯一性得证后，加法和乘法的合理性得证。加法、乘法其他性质继承环R，从而商环的确是一个环。
商环的0元是理想！
我们来看看整数环的商环，我们知道所有的偶数构成的子环是其理想。
那么商环为{{偶数},{奇数}}
四则运算如下：
{偶数} + {偶数} = {偶数} {偶数} - {偶数} = {偶数} {偶数} * {偶数} = {偶数}
{偶数} + {奇数} = {奇数} {偶数} - {奇数} = {奇数} {偶数} * {奇数} = {偶数} {偶数} / {奇数} = {偶数}
{奇数} + {偶数} = {奇数} {奇数} - {偶数} = {奇数} {奇数} * {偶数} = {偶数}
{奇数} + {奇数} = {偶数} {奇数} - {奇数} = {偶数} {奇数} * {奇数} = {奇数} {奇数} / {奇数} = {奇数}
显然，这个商环其实是一个2元域。
实际上，对于任何质数p,{x|x是p的整数倍}都是整数环的一个理想，所得商环都是一个p阶素域。
我们的主题是有限域。那么，我们会想，用整数环的商环可以构造任意阶有限域吗？
实际上不行，比如对于{x|x是4的整数倍}这个理想，
商环如下：
{{x|x=4*a, a是整数}, {x|x=4*a+1, a是整数}, {x|x=4*a+2, a是整数}, {x|x=4*a+3, a是整数}}
其中，{x|x=4*a, a是整数}是0元。
{x|x=4*a+2, a是整数} * {x|x=4*a+2, a是整数} = {x|x=4*a, a是整数}
所有这个商环存在零因子，当然不是域。
多项式环
多项式是我们大家熟知的概念，以下都是一元多项式：
1
2x+4
x2+2x+3
3x2+5x2+9
...
所谓的一元就是只有一个未知数，在这里我就不对于一元多项式给出一个严格的定义了，直接解释多项式环。
所谓一个环A的多项式环B，指的是如下：
(1) B的每个元是一个一元多项式
(2) B的每个元(一元多项式)的每一个系数都是A上的元
(3) 系数全是A上的元的一元多项式都是B的元
多项式的加法、减法就是合并同类项，因为系数取自一个环，所以系数间的加法、减法是合法的，会得到别的多项式。
同样，多项式的乘法要麻烦一点，不过也是得到多项式的。多项式的乘法是利用分配律，展开各项。以下整系数多项式的例子可以让我们回忆起多项式的乘法：
(x2+2x+3) * (3x+5)
= (x2+2x+3) * 3x + (x2+2x+3) * 5
= x2 * 3x + 2x * 3x + 3 * 3x + x2 * 5 + 2x * 5 + 3 *5
= 3x3 + 6x2 + 9x + 5x2 + 10x + 15
= 3x3 + 11x2 + 19x + 15
因为系数都在一个环里，所有乘法、加法都是封闭的，所以多项式乘法也是一样合法的。
所以多项式环当然是环。
可能有的人想问，为什么这里非要用一元多项式？
其实我们在刚才的多项式环定义那里为多项式引入任意多个未知数（甚至无穷多个未知数），其组成的代数系统依然为环，只是多元的多项式环挺复杂，这里不研究。
不可分多项式
我们知道质数是2、3、5、7、11、13、17...这样除了1和本身外没有其他正约数的正整数。
我们在这里对质数做一个引申。
一个多项式环上的任意多项式，当然可以表示为1和自身的乘积，当然也可以表示为-1(1元的相反元)和自身的相反元的乘积，这两者都是很平凡的。
比如：
x2+x+1 = 1 * (x2+x+1)
= -1 * (-x2-x-1)
这都是平凡的，没什么意义。
如果是域上的多项式环，里面任何多项式表示成域上任何一个非0元和一个多项式的乘积。从而，这些也都是平凡的。
而所谓真正意义上的分解，就是要求两个乘积项都不是常数，也就是次数是大于0的。
比如，
x2+2x+1 = (x+1) * (x+1)
不可分解的多项式我们称之为不可分多项式。
比如整数系数下的x2+x+1就是不可分多项式，实际上，即使是2元域（0/1两个元组成的特征2的域）上，这个多项式也是不可分多项式。
但在7元域（0/1/2/3/4/5/6组成的特征7的域）上，
x2+x+1 = (x+3) * (x+5)
多项式的带余除法
我们从小就知道自然数的带余除法，
比如
7÷3 = 2 ... 1
换个写法，7 = 3*2+1
其实，域的多项式环里的多项式也存在这样的带余除法。
对于多项式f和g(g为非0多项式)，一定存在唯一的多项式a和b，满足
f = g*a+b
并且b的次数小于g的次数。
其实证明起来很简单，就如同儿时的竖式除法计算那样，一步步的把高次的项减掉。
比如我们以2阶素域下的多项式 x5+x4+x+1 和 x2+x+1为例
x3 + x +1
_________________________
x2 + x + 1 | x5 + x4 + x + 1
x5 + x4 + x3
______________
x3 + x
x3 + x2 + x
___________
x2 + 1
x2 + x + 1
____________
x
所以，
x5+x4+x+1 = (x2+x+1) * (x3+x+1) + x
带余除法对于后面的理解有至关重要的作用。
有限域
既然想通过商环的方法构造域，那么当然要先考虑多项式环的理想。
我们依然使用生成元的方法去研究。
我们以 p阶素域 作为原本的环 A， 那么A的多项式环称为 B
我们考虑由多项式 f 生成的理想，我们假设 f 是可以分解的，f = f1 * f2。
f1、f2并不在理想里，很明显，f1、f2的次数比f都低，不存在f乘以一个多项式得到f1 或 f2。
我们再回忆一下商环的运算，根据f = f1 * f2，我们有
商集(f1) * 商集(f2) = 商集(f)
商集(f)其实就是理想，也就是商环里的0元，
从而左边两个非0元乘法得到右边的0元，于是这个商环不是整环，当然更不可能是域了。
于是我们考虑由单个不可分多项式生成的理想。
考虑其下一个m次不可分多项式 f（最高未知数次数为m）生成的理想 C ,
然后我们考虑商环B/C长什么样。
理想C其实是所有以多项式 f 为因子的多项式的集合。
我们考虑所有次数小于m的多项式，根据排列组合的乘法原理，这样的多项式一共有pm个。
对于任意两个不同的次数小于m的多项式，假设为g和h。
g-h为非0的次数小于m的多项式，从而g-h不可能以f为因子，从而g-h不在理想里，从而g和h一定属于不同的商集。
因为g和h选择的随意性，从而这pm个多项式分属于pm个不同的商集。
上面介绍过带余除法，考虑次数大于等于m的多项式，假设有一个这样的多项式h,
一定存在一个多项式a和一个次数小于m的多项式b，使得
h = g*a+b
h-b = g*a
g*a在理想C里，于是h和b在同一个商集里。
由于h选择的随意性，从而任何一个次数大于等于m的多项式都落在那pm个不同的商集里。
所以，我们最终的这个商环也就有pm个元。
这里多项式乘法的可交换性遗传自域乘法的可交换，从而这个商环可交换是必然的。
另外，f的不可分特性导致了如果任意g、h不以f为因子，则g*h也不以f为因子。从而，这个商环是一个整环。
有限的可交换整环，因为其有限性，那么当然是除环，从而当然就是域啦（其实，并不存在有限的不可交换整环，不过这个定理证明有那么点麻烦）。
OK,我们终于找到了构造任意阶有限域的方法。
我们可以用这pm个次数小于m的多项式来代表这个域的各个元素。加法、减法就是合并同类项。
乘法就是多项式乘法结果再利用带余除法除以多项式 f 得到的余数。
我们来举个例子。
x2+x+1 是 2阶素域下的不可分多项式。
利用刚才的手段得到了一个4阶域，我们可以记该域下的4个元为
[0]
[1]
[x]
[x+1]
其四则运算为
[0] + [0] = [0] [0] - [0] = [0] [0] * [0] = [0]
[0] + [1] = [1] [0] - [1] = [1] [0] * [1] = [0] [0] / [1] = [0]
[0] + [x] = [x] [0] - [x] = [x] [0] * [x] = [0] [0] / [x] = [0]
[0] + [x+1] = [x+1] [0] - [x+1] = [x+1] [0] * [x+1] = [0] [0] / [x+1] = [0]
[1] + [0] = [1] [1] - [0] = [1] [1] * [0] = [0]
[1] + [1] = [0] [1] - [1] = [0] [1] * [1] = [1] [1] / [1] = [1]
[1] + [x] = [x+1] [1] - [x] = [x+1] [1] * [x] = [x] [1] / [x] = [x+1]
[1] + [x+1] = [x] [1] - [x+1] = [x] [1] * [x+1] = [x+1] [1] / [x+1] = [x]
[x] + [0] = [x] [x] - [0] = [x] [x] * [0] = [0]
[x] + [1] = [x+1] [x] - [1] = [x+1] [x] * [1] = [x] [x] / [1] = [x]
[x] + [x] = [0] [x] - [x] = [0] [x] * [x] = [x+1] [x] / [x] = [1]
[x] + [x+1] = [1] [x] - [x+1] = [1] [x] * [x+1] = [1] [x] / [x+1] = [x+1]
[x+1] + [0] = [x+1] [x+1] - [0] = [x+1] [x+1] * [0] = [0]
[x+1] + [1] = [x] [x+1] - [1] = [x] [x+1] * [1] = [x+1] [x+1] / [1] = [x+1]
[x+1] + [x] = [1] [x+1] - [x] = [1] [x+1] * [x] = [1] [x+1] / [x] = [x]
[x+1] + [x+1] = [0] [x+1] - [x+1] = [0] [x+1] * [x+1] = [x] [x+1] / [x+1] = [1]
附：上一章有网友提议用LaTeX，嗯，本人确实有点懒，不过后面会考虑的。
另外，很多网上文章这里都写 本原多项式 ，人云亦云，悲哀，一帮只愿去抄书不愿去理解的人啊。
建议还是先去了解一下什么叫本原多项式吧。
同余式
- 作者:Luck
- 链接:https://enblog.top/article/df30ce5e-70f6-4ce1-a775-133f9b117e3c
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。