2-有限域-代数基础-环.ppt13

i i =0 i =0 M M
定义
f (x).g (x)= ( a j bi -j )x i .
i =0 j =0
M
i
设f (x),g (x) F[x],有 0 (f (x)+g (x)) max ( 0 f (x), 0 g (x)) [什么时候<成立?] 0 (f (x).g (x))= 0 f (x)+ 0 g (x) 由此可推导出： F[x]中的元素对于所定义的加法和乘法不能成为域. 本章将利用域上的多项式，通过多项式求余和 有理分式的方法来构造域.
系理1 设F 是个域,而F0是F 的一个子域.那么F 的零元和单位元 一定都属于F0 ,而且分别就是F0的零元和单位元. 证：设0是F 的零元， 00是F0的零元. 因为00 F ，所以00 0=00 . 又因为00 F0 , 所以00 00 =00 . 由此， 00 0=00 00，所以0=00 . 同样的方法可以证明单位元. 系理2 设F 是个域,a F 而a a 0,那么a -1 0. 证：假定a -1 0, 那么e aa 1 a 0 0, 与域的定义不符.
有 限 域 (Finite Fields)
信息安全实验室
参考书目
• 《代数与编码》万哲先，科学出版社出 版，华中科技大学出版社影印。
• 《有限域》冯克勤，走向数学丛书，湖 南教育出版社。 • 《近世代数》熊全淹，武汉大学出版社。
一、域的基本性质
1.0 有限域的起源
•17世纪起，费尔马(Fermat,1601-1665)、欧拉(Euler,17071783),勒让德(Legendre,1752-1833)和高斯(Gauss,17771855)等大数学家研究数论得到了同余式的许多性质，实质上 也就研究了p元有限域的许多性质。 •第一个明确讨论任意有限域的是法国年青数学家伽罗华 (Galois,1811-1832),1828年《关于五次方程的代数解法问 题》，产生群的概念，1830年《关于数论》在p元有限域的基 础上，利用扩张方法构造了全部可能的有限域。所以有限域 通常也叫伽罗华域。

群同态基本定理
定理： 设f：G→H是群G到群H上的满同态映射，那
么kerf是群的一个正规子群，而且H同构于商群 G/kerf，即G/kerf≌ H。反之，如果N是G的正规子群， 则映射
: G G / N :(a) aN
是G到G/N的满同态，且kerφ=N. 证明思路： 紧扣正规子群和同态的定义
Z，Q，R，C都是数环。
例2：设Z[x]={a0＋a1x＋a2x2＋…＋anxn | aiZ，n≥0为 整数}，则Z[x]是系数为整数的一切x的多项式所组成的集合， Z[x]关于多项式的加法与乘法构成一个环。
一般地，设A是一个数环，A[x]表示系数属于A的一切x 的多项式所成集合，则A[x]关于多项式的加法与乘法构成 一个环。
指数法则：对任意的m，nZ，a，bR，
（1）(am)n=amn； （2）am·an=am＋n。
3．无零因子环
定义1.2.2：设R是一个环，a，bR，若a·b=0，且a≠0和 b≠0，则称a为R的一个左零因子，b为R的一个右零因子。
若一个元素既是左零因子，又是右零因子，则称它为零因子。
例7：求模6的同余类环Z6的所有零因子和单位。 定义1.2.3：设环R不含左、右零因子，则称R为无零因子环。
我们还将a的逆元a1的n次幂记为an，即
n
an a1a1 a1
群的逆元（a1） 1=a
元素的阶
元素的阶 设G为群，a∈G，如果存在整数t， 使得at=1，则这样的最小正整数t定义为a的阶， 记为o(a)。如果这样的t不存在，则a的阶定义 为∞。
定理： o(a)=m，an=1当且仅当m|n。 证明思路： 充分性显然。必要性围绕着m为
R是无零因子环充要条件是：a，bR，ab=0a=0或 b=0。 环中无左（右）零因子的充要条件是乘法消去律成立，即： a≠0，ab=acb=c；a≠0，ba=cab=c。

一般地，由 c = gcd(a, b)可得： 对每一素数p， cp = min(ap, bp)
PPT课件
数论基础
第8页/共131页
►素数与互素
如果 gcd(a, b) = 1，则称 a 和 b 互素 整数 a, b 互素是指除 1 之外它们没有其它公因子，
例如：8 与15 互素
8 的因子：1, 2, 4, 8 15 的因子：1, 3, 5, 15 1 是 8 与15 唯一的公因子
PPT课件
数论基础
第6页/共131页
►素数与互素
称 c 是两个整数 a、b 的最大公因子，当且仅当： ① c 是 a 的因子也是 b 的因子， 即 c 是 a、b 的公因子 ② a 和 b 的任一公因子，也是 c 的因子
表示为 c = gcd(a, b)
PPT课件
数论基础
第7页/共131页
#: if Y3=妨0设thbe<na）re，tu即rn存X在3x=(gxc<da()f，, d使)；得nbox≡i1nvmeordsea;。 if Y►3=扩1展thEenucrliedtu算r法n 可Y求3=出gcdgc(df,(ad,)b；)，Y当2=gdc-d1 (ma,obd) =f;1， Q=X3还/Y得3到；b 的逆元。 (T1, T2, T3)←(X1-QY1, X2-QY2, X3-QY3); (X1, X2, X3)←(Y1, Y2, Y3); (Y1, Y2, Y3)←(T1, T2, T3); goto #;
3
x4
都有54乘00法逆54 元20。74
0 4
4 1
0 6
4 3
667012345 606420642
770123456 707654321 PPT课件

g(x) r(x) mod f(x)
Fp[x]模 f(x)的全体两两不同余的代表元为
Байду номын сангаасpn
{r(x) Fp[x] | r(x) = 0 或deg(r(x)) < n第三} 单7元 第十课
成才之路 ·高中新课程 ·学习指导 ·人教版 ·语文·必修2
设 f(x)是Fp上的n次不可约多项式 F = {r(x)Fp[x] | r(x) = 0 或deg(r(x)) < n } 多项式的加 : g(x) + h(x)
模 f(x)的乘法: g(x)h(x) (mod f(x))
是否域？
F关于加法构成群 F\{0}关于乘法构成群 F是 pn元有限域
Fp[x]/(f(x)) F
第三单8元 第十课
成才之路 ·高中新课程 ·学习指导 ·人教版 ·语文·必修2
16元有限域F24 f(x) = x4 + x +1是F2上的不可约多项式
第三单12元 第十课
成才之路 ·高中新课程 ·学习指导 ·人教版 ·语文·必修2
本原元（ primitive element ） 乘法群Fq*的生成元称为Fq中的本原元。
Fq中有(q1)个本原元
第三单13元 第十课
成才之路 ·高中新课程 ·学习指导 ·人教版 ·语文·必修2
Fp上n次不可约多项式的存在性 定理 设有限域Fr是Fq的扩域，则Fr是Fq上的单代数扩张 。
证明
设
q

3，q

1

r e1
1
r e2 2

r en n
.
多项式 x(q1)/ri 1在 Fq 中至多有(q1)/ri 个根

f(x)+g(x)= fn xn+…+fm+1xm+1+ (fm + gm)xm+…+ (f1 + g1)x+(f0 + g0)
多项式乘
f(x) g(x)=hn+m xn+m+ hn+m-1 xn+m-1+…+ h1x+h0
i f j gi j i 0,1, , m, n m j 0 hi i f j gi j i m 1, , m n j i m
f ( x) x9 x8 x 7 x 2 x 1 ( x5 x3 x)( x 4 x 3 x 1) ( x 3 1) g ( x) x 4 x3 x 1 ( x 1)( x3 1)
f ( x), g ( x) x3 1 1f ( x) ( x5 x3 x)( x 4 x3 x 1)
x 1:1+x
对所定义的加法和乘法运算， 0,1, x, x 1 构成域
结论：若n次首一多项式f(x)在域Fp上既约，则f(x) 的剩余类环构成一个有pn个元素的有限域
主理想环与同构
多项式环Fp[x]的一切理想均是主理想 多项式剩余类环Fp[x]/f(x)中的每一个理想都是主 理想。且该主理想的生成元必除尽f(x)
群
设G是一个非空集合，并在G内定义了一种代数运算 “ 。”，若满足：
1) 封闭性。对任意 a, b G ，恒有 a b G a, b, c G，恒有 a b c a b c 2) 结合律。对任意 3) G中存在一恒等元e,对任意 a G ，使 a e e a a

• 类似的有环同态基本定理
第16页/共49页
概念的类比
群 正规子群 循环群 商群
环 理想 主理想 商环
第17页/共49页
域的定义
• 域(Field)
▫ 非空集合F，若F中定义了加和乘两种运算，且满足：
1) F关于加法构成阿贝尔群，加法恒等元记为0 2) F中所有非零元素对乘法构成阿贝尔群，乘法恒等元记为1 3) 加法和乘法之间满足分配律
a4
4
0110
x2 +x
a5
5
1100
x3 +x2
a6
6
第39页/共49页
指数形式
4位向量形式 多项式形式 生成元幂形式
1011
x3+x+1
a7
7
0101
x2+1
a8
8
1010
x3 +x
a9
9
0100
x2
a10
10
0111
x2+x+1
a11
11
1110
x3+x2+x
a12
12
1111
x3+x2 +x+1
第31页/共49页
利用不可约多项式构造域
• 令F是一个域，f(x)是F[x]中的一个非零多项式，那么F[x]/f(x)是一个环，当且 仅当 f(x)在F上不可约时， F[x]/f(x)是一个域.
第32页/共49页
• f(x)是F[x]中的一个不可约多项式， 当F是域时， F[x]/f(x)是一个域. 将f(x)称 为域F[x]/f(x)的定义多项式.
n1 11 1＝0
n个1

R=n
15
Ring

特征(Characteristic)
定理
设 R 是整环并且char R > 0, 则 R 的特征是素数.
定理
有限域的特征是素数.
16
Ring

特征(Characteristic)
设
R 是环, R 的特征是素数 p, 则对任意的a, bR 和
nN 有
(a b) a b
pn
pn
pn
和 (a b) a b
pn
pn
pn
17
Ring

例
Z/(n)

= {0,1,…, n1}, 模n加法, 模n乘法
整环? 域? 特征?
整数Z,

整数加法, 整数乘法
整环? 域?
特征?
素理想? 极大理想?
18

例
设K是域,
K[x]是否环?
19
成环, 则 S 称为 R 的子环.
设
R 是交换环, I 是 R 的一个子环, 若下述条件成立 a I 且 r R ar I .
则 I 称为 R 的理想.
6
Ring

理想（Ideal）
有限生成的理想

X = {a1, a2, …, ak} I = {r1a1 + r2a2 + + rkak | aiX, riR}
Ker f
= {rR | f (r) = 0} 是 R 中的理想.
Im
f = {s S | 存在rR 使得s = f (r)}
13
Ring

环同态(Homomorphism of rings)