注：本文章适合学习信息安全数学基础的同学们考前突击，不适用于数学系专业的同学。里面有些内容可能对于数学系来说是不严谨的，但对于信息安全专业为了应付考试的同学来说是完全够用的。
近世代数部分很多同学不会做的根本原因就在于基本性的概念没有搞懂，而信息安全数学基础这门课来说，它不会像数学系一样考特别难的证明（工科主要还是应用为主），因此复习的重点就在于了解所有的概念。而不是去背题。
这篇文章完全是自己总结的，主要是梳理一下概念性的东西、总结一些证明题的解题方法，构建完整的证明思路，考虑到网上资源较少，自己暑假又闲得无聊，那就写个造福一下学弟学妹们。
第11章主要讲到了
先放个图片镇楼。然后步入正题
1 多项式的基本定义和基本运算 1.1 多项式的基本定义对于多项式
f
(
x
)
=
∑
i
=
0
n
a
i
x
i
,
a
n
≠
0
f(x)=sum_{i=0}^na_ix^i,a_n≠0
f(x)=∑i=0naixi,an=0 。其
x
x
x 中次数最高的项即为该多项式
f
(
x
)
f(x)
f(x) 的次数，如
x
3
+
3
x
+
4
x^3+3x+4
x3+3x+4 的次数为
3
3
3，
x
8
+
x
4
+
x
3
+
x
2
+
1
x^8+x^4+x^3+x^2+1
x8+x4+x3+x2+1 的次数为
8
8
8。一般用
deg
f
deg f
degf 表示，规定
deg
0
=
−
∞
deg 0=-∞
deg0=−∞
多项式之间不可以比较大小，只有其次数可以比较大小。
多项式一般会定义在环上，比如整数环
Z
Z
Z，实数环
R
R
R，也可以定义在
F
p
mathbb F_p
Fp，
Z
m
Z_m
Zm 上。
举个例子：多项式环
Z
[
x
]
Z[x]
Z[x] 表示定义在整数环上的多项式环，多项式的字母是
x
x
x，其所有系数均为整数。因此有
x
3
+
4
x
+
1
∈
Z
[
x
]
x^3+4x+1in Z[x]
x3+4x+1∈Z[x]，
x
4
+
0.3
x
3
−
0.7
∉
Z
[
x
]
x^4+0.3x^3-0.7not in Z[x]
x4+0.3x3−0.7∈Z[x]，但
x
4
+
0.3
x
3
−
0.7
∈
R
[
x
]
x^4+0.3x^3-0.7 in R[x]
x4+0.3x3−0.7∈R[x]。
多项式与多项式之间，也可以进行加法和乘法的操作，但对于不同的多项式，需要注意其系数所在的环的不同，比如同样是 f ( x ) = x 4 + x 3 + x + 1 f(x)=x^4+x^3+x+1 f(x)=x4+x3+x+1， g ( x ) = 2 x 3 + 3 x 2 + 5 g(x)=2x^3+3x^2+5 g(x)=2x3+3x2+5，若其定义在整数环上，则两者相加的结果为 x 4 + 3 x 3 + 3 x 2 + x + 6 x^4+3x^3+3x^2+x+6 x4+3x3+3x2+x+6，若其定义在 F 3 mathbb F_3 F3 上，结果为 x 4 + x x^4+x x4+x，所有系数均模 3 3 3 处理了，若其定义在 Z 4 Z_4 Z4 上，相加的结果为 x 4 + 3 x 3 + 3 x 2 + x + 2 x^4+3x^3+3x^2+x+2 x4+3x3+3x2+x+2，所有的结果模 4 4 4 处理。其乘法也具有类似的特点。
1.3 多项式的求根运算例1：计算 f ( x ) = x 4 + 2 x 3 + 4 , g ( x ) = x 3 + 4 x 2 + 3 f(x)=x^4+2x^3+4,g(x)=x^3+4x^2+3 f(x)=x4+2x3+4,g(x)=x3+4x2+3 的乘积，分别在 Z [ x ] Z[x] Z[x] 上和 F 7 [ x ] mathbb F_7[x] F7[x] 上给出结果
Z [ x ] Z[x] Z[x] 上结果： x 7 + 6 x 6 + 8 x 5 + 3 x 4 + 10 x 3 + 16 x 2 + 12 x^{7} + 6 , x^{6} + 8 , x^{5} + 3 , x^{4} + 10 , x^{3} + 16 , x^{2} + 12 x7+6x6+8x5+3x4+10x3+16x2+12
F 7 [ x ] mathbb F_7[x] F7[x] 上结果： x 7 + 6 x 6 + x 5 + 3 x 4 + 3 x 3 + 2 x 2 + 5 x^7 + 6x^6 + x^5 + 3x^4 + 3x^3 + 2x^2 + 5 x7+6x6+x5+3x4+3x3+2x2+5，可以看到所有的系数均在模 7 7 7 的意义下处理过了。
最高项次数为
1
1
1 的多项式叫做首
1
1
1 多项式。
多项式的根为使得
f
(
x
)
=
0
f(x)=0
f(x)=0 满足的
x
x
x 的取值，比如
F
17
mathbb F_{17}
F17 上，
x
3
+
4
x
+
1
=
0
x^3+4x+1=0
x3+4x+1=0 的根只有一个
x
=
7
x=7
x=7，但多项式
x
3
+
4
x
+
12
=
0
x^3+4x+12=0
x3+4x+12=0 的解却有三个：
x
=
1
,
3
,
12
x=1,3,12
x=1,3,12。
2 多项式的一些特殊运算定理：定义在域上的 n n n 多项式，最多有 n n n 个根。这里的域可以是 Q , R mathbb Q,R Q,R ，也可以是有限域 F p mathbb F_p Fp 甚至 F p a mathbb F_{p^a} Fpa。
之前我们提到过，多项式也是一种特殊的数，因此类比我们学过的内容，除了基本运算外，之前课程中学到的各种内容也可以扩展到多项式上：
2.1 多项式环上的带余除法：第一章有：对于任意一个数
n
n
n，我们有
n
=
a
m
+
r
n=am+r
n=am+r，其中
a
a
a 定义为商，
m
m
m 定义为除数，
r
r
r 定义为余数。即：
n
÷
m
=
a
.
.
.
.
.
.
r
n÷m=a ... ...r
n÷m=a......r。一般要求余数取值范围为
0
0
0 到
m
−
1
m-1
m−1。 例：分别在在
Z
[
x
]
Z[x]
Z[x] 和
F
7
mathbb F_7
F7上，设
f
(
x
)
=
x
6
+
x
4
+
3
x
+
1
,
m
(
x
)
=
x
4
+
x
+
3
f(x)=x^6+x^4+3x+1,m(x)=x^4+x+3
f(x)=x6+x4+3x+1,m(x)=x4+x+3，设
f
f
f 为被除式，
m
m
m 为除式，求商式
g
g
g 和余式
r
r
r 。 若
r
(
x
)
=
0
r(x)=0
r(x)=0，则称
f
(
x
)
f(x)
f(x) 整除
m
(
x
)
m(x)
m(x)，用
m
(
x
)
∣
f
(
x
)
m(x)|f(x)
m(x)∣f(x) 表示，比如：
R
[
x
]
R[x]
R[x] 上，
(
x
+
1
)
∣
(
x
3
+
3
x
2
+
3
x
+
1
)
(x+1)|(x^3+3x^2+3x+1)
(x+1)∣(x3+3x2+3x+1)。 在第一章，我们了解到，对于一个数
n
n
n ，若除了
1
1
1 和它本身之外，没有任何因数，则该数为素数。 在第一章，我们知道，对于任何一个合数
n
n
n，可以唯一的表示成
n
=
p
1
a
1
p
2
a
2
.
.
.
.
.
.
p
k
a
k
n=p_1^{a_1}p_2^{a_2}... ...p_k^{a_k}
n=p1a1p2a2......pkak，其中
p
p
p 是素数。 在第一章，我们了解到：对于任何一个数
p
p
p ，若
2
2
2 到
p
sqrt p
p
中的每一个整数都不能整除
n
n
n，则
p
p
p 是素数。 推论：对于所有的二次和三次不可约多项式
f
(
x
)
f(x)
f(x)，方程
f
(
x
)
=
0
f(x)=0
f(x)=0 无解，使用该方法可以快速判断二、三次多项式是否不可约。 当然，判断一个多项式是否可约，也需要注意多项式所在的多项式环，也就是所有系数的定义域。比如对于
f
(
x
)
=
x
8
+
x
4
+
x
3
+
x
+
1
f(x)=x^8+x^4+x^3+x+1
f(x)=x8+x4+x3+x+1，其在
F
2
mathbb F_2
F2 上是不可约多项式，但在
F
7
mathbb F_7
F7 上可以分解成
(
x
3
+
6
x
+
2
)
⋅
(
x
5
+
x
3
+
5
x
2
+
2
x
+
4
)
(x^{3} + 6 x + 2) cdot (x^{5} + x^{3} + 5 x^{2} + 2 x + 4)
(x3+6x+2)⋅(x5+x3+5x2+2x+4)。 在第一章，我们了解到：对于任意素数
p
p
p 和整数
a
a
a，若
p
∤
a
p not | a
p∣a，则
(
p
,
a
)
=
1
(p,a)=1
(p,a)=1。 这里需要补充说明的一点是，多项式的最大公因式一般理解为次数最高的首
1
1
1 多项式。因此求多项式的公因式的时候，需要将最终结果化为首
1
1
1 多项式。比如在
Z
[
x
]
Z[x]
Z[x] 上，
(
4
x
+
4
,
6
x
+
6
)
=
x
+
1
(4x+4,6x+6) = x+1
(4x+4,6x+6)=x+1。 在第一章，我们知道，对于给定的正整数
a
,
b
a,b
a,b，若
(
a
,
b
)
∣
n
(a,b)|n
(a,b)∣n，则存在整数
s
,
t
s,t
s,t 使得
n
=
s
a
+
t
b
n=sa+tb
n=sa+tb 成立。 结合不可约多项式的性质：对于任意不可约多项式
p
(
x
)
p(x)
p(x) 和一般多项式
f
(
x
)
f(x)
f(x)，若
p
(
x
)
∤
f
(
x
)
p(x) not | f(x)
p(x)∣f(x)，则
(
p
(
x
)
,
f
(
x
)
)
=
1
(p(x),f(x))=1
(p(x),f(x))=1。我们可以发现：任何不整除
p
(
x
)
p(x)
p(x) 的多项式
f
(
x
)
f(x)
f(x) 都可以使用exgcd算法，求出
f
−
1
(
x
)
m
o
d
p
f^{-1}(x) mod p
f−1(x)modp值。 例：已知
p
(
x
)
=
x
3
+
x
+
1
p(x)=x^3+x+1
p(x)=x3+x+1 是
F
7
[
x
]
mathbb F_7[x]
F7[x] 上的不可约多项式，求
f
(
x
)
=
(
x
2
+
4
x
+
5
)
f(x)=(x^2+4x+5)
f(x)=(x2+4x+5) 模
p
(
x
)
p(x)
p(x) 的逆元。 留一个练习题，请自己计算： 在
F
2
mathbb F_2
F2 上，
p
(
x
)
=
x
8
+
x
4
+
x
3
+
x
+
1
p(x)=x^8+x^4+x^3+x+1
p(x)=x8+x4+x3+x+1，
f
(
x
)
=
x
7
+
x
3
+
x
f(x)=x^7+x^3+x
f(x)=x7+x3+x,求
f
(
x
)
f(x)
f(x) 模
p
(
x
)
p(x)
p(x) 的逆元。 注：实际上多项式的除法，可以将相同次数对应的系数对齐，列竖式计算。如下图，这样得出商式为
x
+
3
x+3
x+3，余式为
5
x
5x
5x。 构造方法：寻找
F
p
[
x
]
mathbb F_p[x]
Fp[x] 中的一个
a
a
a 次 不可约 多项式
P
(
x
)
P(x)
P(x)即可，组成的有限域可以表示为：
F
p
a
=
F
p
[
x
]
/
(
P
(
x
)
)
mathbb F_{p^a}=mathbb F_p[x]/(P(x))
Fpa=Fp[x]/(P(x))。
F
2
mathbb F_2
F2: 例题1：构造有限域
F
4
mathbb F_4
F4，可以使用的多项式是什么： 下面展示一下两种不同构造下
F
9
mathbb F_9
F9 的加法和乘法运算表，来直观感受下这个域是什么样子。 在介绍本原多项式之前，我们继续讨论下不可约多项式的一些性质。 费马小定理告诉我们：若
p
p
p 是素数，则
a
p
=
a
(
m
o
d
p
)
a^p=apmod p
ap=a(modp)。若
b
≠
0
b not =0
b=0，则有
b
p
−
1
=
1
(
m
o
d
p
)
b^{p-1}=1pmod p
bp−1=1(modp) 成立。即在域
F
p
mathbb F_p
Fp 中，若
b
≠
0
bnot =0
b=0，则
b
p
−
1
=
1
b^{p-1}=1
bp−1=1。 在之前，我们还引入了原根的概念。以
F
11
mathbb F_{11}
F11 为例，虽然
1
1
1 到
10
10
10 中，任何一个元素的
10
10
10 次方模
11
11
11 的值均为
1
1
1，但有的元素比较特殊，比如
1
,
10
,
3
1,10,3
1,10,3，因为有
1
1
,
1
0
2
,
3
5
1^1,10^2,3^5
11,102,35 在
F
11
mathbb F_{11}
F11 中的值就已经是
1
1
1 了。而有的元素，比如
2
2
2，其
1
,
2
,
5
1,2,5
1,2,5 次方均不等于
1
1
1，必须要达到
10
10
10 次方其值才等于
1
1
1。因此
2
2
2 是
11
11
11 的一个原根。 若
a
a
a 是模
p
p
p 原根，则
a
p
−
1
=
1
a^{p-1} =1
ap−1=1 成立，且对于
p
−
1
p-1
p−1 的所有除
p
−
1
p-1
p−1 本身因数
k
k
k，均要有
a
k
≠
1
a^{k}not =1
ak=1成立。 比如我们要判断
3
3
3 是不是
61
61
61 的原根，可以这样做：先将
61
−
1
=
60
61-1=60
61−1=60 进行质因数分解，得到
60
=
2
2
×
3
×
5
60=2^2×3×5
60=22×3×5，然后判断
3
60
÷
2
,
3
60
÷
3
,
3
60
÷
5
3^{60÷2},3^{60÷3},3^{60÷5}
360÷2,360÷3,360÷5 模
61
61
61 是否为
1
1
1 即可。若这三个值均不为
1
1
1，则
3
3
3 是
61
61
61 的原根。 那我们来做一道题看看： 在
F
2
[
x
]
mathbb F_2[x]
F2[x] 中 因此我们可以得出定义：若
x
x
x 是不可约多项式
p
(
x
)
p(x)
p(x) 的原根，则称
p
(
x
)
p(x)
p(x) 为本原多项式。本原多项式在密码学中有非常广泛的用途，比如最长异或序列LFSR的构造。但对于有限域而言，只要求是不可约多项式即可，不必是本原多项式。 因此，证明
F
p
[
x
]
mathbb F_p[x]
Fp[x] 上一个
a
a
a次多项式 是否为本原多项式，首先将
p
a
−
1
p^a-1
pa−1 分解质因数。然后证明
x
p
a
−
1
x^{p^a-1}
xpa−1 值为
1
1
1，且
p
a
−
1
p^a-1
pa−1 除以其每一个素因数的结果作为
x
x
x 的指数时，得出的每一个结果均不为
1
1
1 即可。 证明：
x
2
+
1
x^2+1
x2+1 不是
F
3
[
x
]
mathbb F_3[x]
F3[x] 上的本原多项式： 证明：
x
4
+
x
2
+
3
x
+
2
x^4+x^2+3x+2
x4+x2+3x+2 是
F
5
mathbb F_5
F5 上的
4
4
4 次本原多项式： 拓展：任何一个不可约多项式实际上都有原根，但本原多项式必须要求
x
x
x 是其原根。至于我们上面谈到的
F
3
[
x
]
mathbb F_3[x]
F3[x] 中的不可约多项式
x
2
+
1
x^2+1
x2+1，虽然
x
x
x 不是其原根，但
x
+
1
x+1
x+1 是其原根，且
(
x
+
1
)
6
≡
x
(
m
o
d
x
2
+
1
)
(x+1)^6equiv xpmod{x^2+1}
(x+1)6≡x(modx2+1)。由于要求指数是
8
8
8，此处
6
6
6 与
8
8
8 的最大公因数不是
1
1
1，因此
x
x
x 就不是其原根了。 多项式理想的知识点，可以直接按照之前讲到的理想的方法来做，简单做一下了解就可以了，这一部分在数上也不是重点。 根据极大理想和素理想的定义，我们可以得知：极大理想一定是素理想，素理想不一定是极大理想。 因此，我们找到了一个素理想不是极大理想的反例。 信安数基实际上跟密码学联系挺大的，因此可以自行了解一些密码学的知识，这样也许会对学信安数基有所帮助~ flag{Dui4Yu2Mi4Ma3Lao3,Gao1Shu4Guo4Yu2Jian3Dan1Wu2Liao2}
对于多项式，也可以利用这种方法：即
f
(
x
)
f(x)
f(x) 可以写为
f
(
x
)
=
g
(
x
)
m
(
x
)
+
r
(
x
)
f(x)=g(x)m(x)+r(x)
f(x)=g(x)m(x)+r(x) 其中
g
(
x
)
g(x)
g(x) 定义为商式，
m
(
x
)
m(x)
m(x) 定义为除式，
r
(
x
)
r(x)
r(x) 定义为余式。要求余式的次数要严格小于除式，即
deg
r
<
deg
m
deg r
步骤：先配置
x
6
x^6
x6 ，为
x
6
=
x
2
(
x
4
+
x
+
3
)
−
x
3
−
3
x
2
x^6=x^2(x^4+x+3)-x^3-3x^2
x6=x2(x4+x+3)−x3−3x2。
再配置
x
4
x^4
x4，为
x
4
=
x
4
+
x
+
3
−
x
−
3
x^4=x^4+x+3-x-3
x4=x4+x+3−x−3。
因此原式可以写为
f
(
x
)
=
(
x
2
+
1
)
(
x
4
+
x
+
3
)
−
x
3
−
3
x
2
−
x
−
3
+
3
x
+
1
f(x) =(x^2+1)(x^4+x+3)-x^3-3x^2-x-3+3x+1
f(x)=(x2+1)(x4+x+3)−x3−3x2−x−3+3x+1。
合并同类项，得
f
(
x
)
=
(
x
2
+
1
)
(
x
4
+
x
+
3
)
−
x
3
−
3
x
2
+
2
x
−
2
f(x)=(x^2+1)(x^4+x+3)-x^3-3x^2+2x-2
f(x)=(x2+1)(x4+x+3)−x3−3x2+2x−2。
因此在
Z
[
x
]
Z[x]
Z[x] 上：
g
(
x
)
=
x
2
+
1
g(x)=x^2+1
g(x)=x2+1，
r
(
x
)
=
−
x
3
−
3
x
2
+
2
x
−
2
r(x)=-x^3-3x^2+2x-2
r(x)=−x3−3x2+2x−2，可以看到
deg
r
<
deg
m
deg r
2.2 多项式环上的因式、不可约多项式(素式)：
F
2
[
x
]
mathbb F_2[x]
F2[x] 上，
(
x
+
1
)
∣
(
x
3
+
x
2
+
x
+
1
)
(x+1)|(x^3+x^2+x+1)
(x+1)∣(x3+x2+x+1)
你能发现上面两个式子的关系吗？
这里我们还可以定义：对于一个首1多项式
f
(
x
)
f(x)
f(x) ，若除了
1
1
1 和它本身之外，没有任何因式，则该数为不可约多项式。
这里我们还可以扩展到多项式：对于任何一个多项式
f
(
x
)
f(x)
f(x)，可以唯一地表示成
f
(
x
)
=
p
1
a
1
(
x
)
p
2
a
2
(
x
)
.
.
.
.
.
.
p
k
a
k
(
x
)
f(x)=p_1^{a_1}(x)p_2^{a_2}(x)... ...p_k^{a_k}(x)
f(x)=p1a1(x)p2a2(x)......pkak(x)，其中
p
(
x
)
p(x)
p(x) 是不可约多项式。
这条性质仍然可以扩展到多项式：对于任何一个多项式
f
(
x
)
f(x)
f(x)，若
1
1
1 次到
n
2
frac n 2
2n 次的所有多项式都不能整除该多项式，则
f
(
x
)
f(x)
f(x) 是不可约多项式，所有的
1
1
1 次多项式都是不可约多项式。
该性质可以推广到多项式上：对于任意不可约多项式
p
(
x
)
p(x)
p(x) 和一般多项式
f
(
x
)
f(x)
f(x)，若
p
(
x
)
∤
f
(
x
)
p(x) not | f(x)
p(x)∣f(x)，则
(
p
(
x
)
,
f
(
x
)
)
=
1
(p(x),f(x))=1
(p(x),f(x))=1。
2.3 多项式上的exgcd算法
该性质仍然可以扩展到多项式层面：对于给定的多项式
f
(
x
)
,
g
(
x
)
f(x),g(x)
f(x),g(x)，若
(
f
(
x
)
,
g
(
x
)
)
∣
n
(
x
)
(f(x),g(x))|n(x)
(f(x),g(x))∣n(x)，则存在两个多项式
s
(
x
)
,
t
(
x
)
s(x),t(x)
s(x),t(x)，使得
n
(
x
)
=
s
(
x
)
f
(
x
)
+
t
(
x
)
g
(
x
)
n(x)=s(x)f(x)+t(x)g(x)
n(x)=s(x)f(x)+t(x)g(x)。
解：根据 bezout 等式和exgcd算法，有：
x
3
+
x
+
1
x^3+x+1
x3+x+1
=
(
x
3
+
4
x
2
+
5
x
)
+
3
x
2
+
3
x
+
1
=(x^3+4x^2+5x)+3x^2+3x+1
=(x3+4x2+5x)+3x2+3x+1（三次式除以二次式为一次式，因此先凑个
x
x
x 出来，）
=
x
(
x
2
+
4
x
+
5
)
+
3
(
x
2
+
4
x
+
5
)
−
9
x
−
14
=x(x^2+4x+5)+3(x^2+4x+5)-9x-14
=x(x2+4x+5)+3(x2+4x+5)−9x−14 （上面余了个二次式，由于除式是二次式，因此还需要凑个常数。并通过结余配平式子）
=
(
x
+
3
)
(
x
2
+
4
x
+
5
)
+
5
x
=(x+3)(x^2+4x+5)+5x
=(x+3)(x2+4x+5)+5x （由于是
F
7
mathbb F_7
F7 上的运算，因此
−
9
x
−
14
-9x-14
−9x−14 模
7
7
7 后化为
5
x
5x
5x）
因此有：
x
3
+
x
+
1
=
(
x
+
3
)
(
x
2
+
4
x
+
5
)
+
5
x
x^3+x+1=(x+3)(x^2+4x+5)+5x
x3+x+1=(x+3)(x2+4x+5)+5x。
然后利用辗转相除法，下一步计算：
(
x
2
+
4
x
+
5
)
=
(
3
x
+
5
)
⋅
5
x
+
5
(x^2+4x+5)=(3x+5)·5x+5
(x2+4x+5)=(3x+5)⋅5x+5。
最后的余式是
5
5
5。即
(
x
3
+
x
+
1
,
x
2
+
4
x
+
5
)
=
5
(x^3+x+1,x^2+4x+5)=5
(x3+x+1,x2+4x+5)=5，由于一般公约式结果化为首
1
1
1 多项式，因此也可以说
(
x
3
+
x
+
1
,
x
2
+
4
x
+
5
)
=
1
(x^3+x+1,x^2+4x+5)=1
(x3+x+1,x2+4x+5)=1。
根据上面继续构造等式：
5
=
(
x
2
+
4
x
+
5
)
−
(
3
x
+
5
)
⋅
5
x
=
(
x
2
+
4
x
+
5
)
+
(
4
x
+
2
)
⋅
5
x
5=(x^2+4x+5)-(3x+5)·5x=(x^2+4x+5)+(4x+2)·5x
5=(x2+4x+5)−(3x+5)⋅5x=(x2+4x+5)+(4x+2)⋅5x。 注：此处负号给
3
x
+
5
3x+5
3x+5，因为上面的计算中，
5
x
5x
5x 为中间结果，
(
3
x
+
5
)
(3x+5)
(3x+5) 为系数，因此保留
5
x
5x
5x，对
5
x
5x
5x 的系数
3
x
+
5
3x+5
3x+5 取负。
由于一般要求化成
1
=
.
.
.
1=...
1=... 的形式，上面每个式子左右两边乘上
5
5
5的逆元
3
3
3，得：
1
=
3
(
x
2
+
4
x
+
5
)
+
(
5
x
+
6
)
⋅
(
5
x
)
1=3(x^2+4x+5)+(5x+6)·(5x)
1=3(x2+4x+5)+(5x+6)⋅(5x)
将
5
x
=
(
x
3
+
x
+
1
)
−
(
x
+
3
)
(
x
2
+
4
x
+
5
)
5x=(x^3+x+1)-(x+3)(x^2+4x+5)
5x=(x3+x+1)−(x+3)(x2+4x+5) 带入得：
1
=
3
(
x
2
+
4
x
+
5
)
+
(
5
x
+
6
)
(
x
3
+
x
+
1
)
−
(
5
x
+
6
)
(
x
+
3
)
(
x
2
+
4
x
+
5
)
1=3(x^2+4x+5)+(5x+6)(x^3+x+1)-(5x+6)(x+3)(x^2+4x+5)
1=3(x2+4x+5)+(5x+6)(x3+x+1)−(5x+6)(x+3)(x2+4x+5)
展开结果为
1
=
(
5
x
+
6
)
(
x
3
+
x
+
1
)
+
(
2
x
2
+
6
)
(
x
2
+
4
x
+
5
)
1=(5x+6)(x^3+x+1)+(2x^2+6)(x^2+4x+5)
1=(5x+6)(x3+x+1)+(2x2+6)(x2+4x+5)。
因此，在
F
7
mathbb F_7
F7上，
x
2
+
4
x
+
5
x^2+4x+5
x2+4x+5 模
x
3
+
x
+
1
x^3+x+1
x3+x+1 的逆元为
2
x
2
+
6
2x^2+6
2x2+6。
答案：
x
7
+
x
4
+
x
2
+
1
x^7 + x^4 + x^2 + 1
x7+x4+x2+1。
下面为常见的不可约多项式：
二次：
x
2
+
x
+
1
x^2+x+1
x2+x+1
三次：
x
3
+
x
+
1
,
x
3
+
x
2
+
1
x^3+x+1,x^3+x^2+1
x3+x+1,x3+x2+1。
四次：
x
4
+
x
+
1
,
x
4
+
x
3
+
1
,
x
4
+
x
3
+
x
2
+
x
+
1
x^4+x+1,x^4+x^3+1,x^4+x^3+x^2+x+1
x4+x+1,x4+x3+1,x4+x3+x2+x+1。
八次：
x
8
+
x
4
+
x
3
+
x
+
1
,
x
8
+
x
4
+
x
3
+
x
2
+
1
x^8+x^4+x^3+x+1,x^8+x^4+x^3+x^2+1
x8+x4+x3+x+1,x8+x4+x3+x2+1。
F
3
mathbb F_3
F3
二次：
x
2
+
1
,
x
2
+
x
+
2
x^2+1,x^2+x+2
x2+1,x2+x+2
三次：
x
3
+
2
x
+
1
x^3+2x+1
x3+2x+1。
F
5
,
F
7
mathbb F_5,mathbb F_7
F5,F7 通用
二次：
x
2
+
2
x^2+2
x2+2
三次：
x
3
+
x
+
1
x^3+x+1
x3+x+1
注：实际上，二次不可约多项式可以通过二次非剩余来构造，比如由于
2
2
2 是模
11
11
11 的二次非剩余，因此
x
2
=
2
x^2=2
x2=2 在模
11
11
11 的意义下无解，因此
x
2
−
2
x^2-2
x2−2 是
F
11
mathbb F_{11}
F11 上的一个二次不可约多项式。
对于二次和三次不可约多项式，也可以通过上面讲到的性质来构造。
答案：
x
2
+
x
+
1
x^2+x+1
x2+x+1，因为
4
=
2
2
4=2^2
4=22，因此使用
F
2
mathbb F_2
F2 上的二次不可约多项式。
例题2：构造有限域
F
8
mathbb F_8
F8，可以使用的多项式是什么：
答案：
x
3
+
x
+
1
x^3+x+1
x3+x+1 或者
x
3
+
x
2
+
1
x^3+x^2+1
x3+x2+1（任意一个都可以）
例题3：构造有限域
F
9
mathbb F_9
F9，可以使用的多项式是什么：
答案：
x
2
+
1
x^2+1
x2+1 或者
x
2
+
2
x
+
2
x^2+2x+2
x2+2x+2
观察上面两张图，可以发现：当所使用的不可约多项式不同的时候，构造出的有限域中，加法规则不变，因为无论两个多项式怎么加，次数都不会溢出。而乘法图就出现了区别：因为当次数溢出后，就需要对其进行取模运算。而取模多项式的不同就会导致取模后的结果不同。因此两个乘法图确实存在一定差别。
观察上面两个图，可以证明我们构造的这一运算法则中，加法构成了交换群，乘法除零元
0
0
0 外，仍构成交换群，因此上面两个图确实是两个九元域，只不过取模多项式不同，导致运算规则不同。
当然，这个性质在
F
p
a
mathbb F_{p^a}
Fpa 中也成立，即在域
F
p
a
mathbb F_{p^a}
Fpa 中，对于任意元素
a
a
a，有
b
p
a
−
1
=
1
b^{p^a-1}=1
bpa−1=1成立。也就是对于
F
p
[
x
]
mathbb F_p[x]
Fp[x] 上的
a
a
a 次不可约多项式
q
(
x
)
q(x)
q(x)，若某多项式
f
(
x
)
f(x)
f(x) 不整除
q
(
x
)
q(x)
q(x)，则
f
p
a
−
1
(
x
)
=
1
(
m
o
d
q
(
x
)
)
f^{p^a-1}(x)=1pmod {q(x)}
fpa−1(x)=1(modq(x)) 成立。
因此我们有了原根的判定方法：
(1)判断
x
x
x 是否为不可约多项式
x
8
+
x
4
+
x
3
+
x
+
1
x^8+x^4+x^3+x+1
x8+x4+x3+x+1的原根
(2)判断
x
x
x 是否为不可约多项式
x
8
+
x
4
+
x
3
+
x
2
+
1
x^8+x^4+x^3+x^2+1
x8+x4+x3+x2+1 的原根。
解：由于这两个不可约多项式均为
F
2
[
x
]
mathbb F_2[x]
F2[x] 中的
8
8
8 次多项式，因此有
f
255
(
x
)
=
1
f^{255}(x)=1
f255(x)=1 模这两个多项式成立。对
255
255
255 进行分解因数，得：
255
=
3
×
5
×
17
255=3×5×17
255=3×5×17。因此我们判断
x
85
,
x
51
,
x
15
x^{85},x^{51},x^{15}
x85,x51,x15 是否为
1
1
1 即可。
当模式为
x
8
+
x
4
+
x
3
+
x
+
1
x^8+x^4+x^3+x+1
x8+x4+x3+x+1时，有：
x
15
=
x
5
+
x
3
+
x
2
+
x
+
1
≠
1
x^{15}=x^5 + x^3 + x^2 + x + 1≠1
x15=x5+x3+x2+x+1=1，
x
51
=
1
x^{51}=1
x51=1 ，因此
x
x
x 的指数为
55
55
55，故
x
x
x 不是模
x
8
+
x
4
+
x
3
+
x
+
1
x^8+x^4+x^3+x+1
x8+x4+x3+x+1的原根。
当模式为
x
8
+
x
4
+
x
3
+
x
2
+
1
x^8+x^4+x^3+x^2+1
x8+x4+x3+x2+1 时，有：
x
15
=
x
5
+
x
2
+
x
x^{15}=x^5+x^2+x
x15=x5+x2+x，
x
51
=
x
3
+
x
x^{51}=x^3+x
x51=x3+x，
x
85
=
x
7
+
x
6
+
x
4
+
x
2
+
x
x^{85}=x^7 + x^6 + x^4 + x^2 + x
x85=x7+x6+x4+x2+x，这三者均不为
1
1
1，因此
x
x
x 是
x
8
+
x
4
+
x
3
+
x
2
+
1
x^8+x^4+x^3+x^2+1
x8+x4+x3+x2+1 的原根。
此处的指数运算，可以使用二分快速幂做，也就是模平方法
证明：
3
2
−
1
=
8
3^2-1=8
32−1=8，
8
8
8 的素因数只有
2
2
2，因此我们计算一下
x
4
x^4
x4 是否等于
1
1
1：
由于
x
2
=
2
(
m
o
d
x
2
+
1
)
x^2 =2 pmod {x^2+1}
x2=2(modx2+1)，那么
x
4
=
2
2
=
1
x^4=2^2=1
x4=22=1，发现
x
4
=
1
x^4=1
x4=1，因此
x
2
+
1
x^2+1
x2+1 不是
F
3
[
x
]
mathbb F_3[x]
F3[x] 的本原多项式
证明：
5
4
=
625
5^4=625
54=625，
624
=
2
4
×
3
×
13
624=2^4×3×13
624=24×3×13，
624
÷
2
=
312
,
624
÷
3
=
208
,
624
÷
13
=
48
624÷2=312,624÷3=208,624÷13=48
624÷2=312,624÷3=208,624÷13=48
可以计算出：
x
624
≡
1
(
m
o
d
x
4
+
x
2
+
3
x
+
2
)
x^{624}equiv 1pmod {x^4+x^2+3x+2}
x624≡1(modx4+x2+3x+2)，
x
312
≡
4
(
m
o
d
x
4
+
x
2
+
3
x
+
2
)
x^{312}equiv 4 pmod {x^4+x^2+3x+2}
x312≡4(modx4+x2+3x+2)
x
208
≡
x
3
+
3
x
2
+
4
x
+
2
(
m
o
d
x
4
+
x
2
+
3
x
+
2
)
x^{208}equiv x^{3} + 3 x^{2} + 4 x + 2 pmod {x^4+x^2+3x+2}
x208≡x3+3x2+4x+2(modx4+x2+3x+2)，
x
48
≡
x
3
+
3
x
2
+
2
x
+
3
(
m
o
d
x
4
+
x
2
+
3
x
+
2
)
x^{48}equiv x^{3} + 3 x^{2} + 2 x + 3 pmod {x^4+x^2+3x+2}
x48≡x3+3x2+2x+3(modx4+x2+3x+2)。因此
x
x
x 的指数为
624
624
624，故
x
4
+
x
2
+
3
x
+
2
x^4+x^2+3x+2
x4+x2+3x+2 是
F
5
mathbb F_5
F5 上的
4
4
4 次本原多项式。
4 多项式理想
不过你们还记得第10章中，有这样一个话吗？
素理想不一定是极大理想。
可以给出这样一个例子：
在多项式环
Z
[
x
]
mathbb Z[x]
Z[x] 中，
(
x
)
(x)
(x) 是该环的一个素理想，因为
Z
[
x
]
/
(
x
)
mathbb Z[x]/(x)
Z[x]/(x)，相当于所有多项式都对
x
x
x 取模，最后得到
Z
mathbb Z
Z，而
Z
mathbb Z
Z 是整环（之前证明过），因此
Z
[
x
]
mathbb Z[x]
Z[x]中，
(
x
)
(x)
(x) 是该环的一个素理想。
但该理想不是极大理想，因为若
(
x
)
(x)
(x)是
Z
[
x
]
mathbb Z[x]
Z[x] 中的一个极大理想，要求
Z
[
x
]
/
(
x
)
mathbb Z[x]/(x)
Z[x]/(x) 中每一个非
0
0
0 元都有乘法逆元。由于根据定义，可以得到：
Z
[
x
]
/
(
x
)
=
Z
mathbb Z[x]/(x)=Z
Z[x]/(x)=Z，但
Z
Z
Z 中并非所有的非
0
0
0 元都有乘法逆元，比如
2
t
=
1
2t=1
2t=1 不存在整数解，因此
2
2
2 没有乘法逆元。因此
(
x
)
(x)
(x) 不是极大理想。
