有限域.

Presentation on theme: "有限域."— Presentation transcript:

1 有限域

2 内容 近世代数基本知识复习 子环与理想 循环群 有限域的乘法结构 有限域的加法结构 有限域的代数结构 多项式的因式分解 正规基和对偶基

3 同余和剩余类 同余 剩余类 若整数a和b被同一正整数m除时，有相同的余数，则称a、b关于模m同余，记为 若 则
若 则 剩余类 给定正整数m，将全体整数按余数相同进行分类，可获得m个剩余类：

4 同态与同构 代数系统 同态与同构： 满足一定规律或定律的系统称为代数系统。且有： 有一群元素构成一个集合； 在元素集合中有一个等价关系；
在集合中定义了一个或数个运算，通过运算建立起元素之间的关系； 有一组假定。 同态与同构： 设f是代数系统(A, · )到(B,*)的映射，如果它满足条件 f(a1 · a2) =f(a1) *f(a2) a1 ,a2 ∈A, f(a1) ,f(a2) ∈B 则称f是A到B的同态映射，集合A与B同态。如果同态 映射f又是双射，则称为同构映射，集合A与B同构。若f是A 到A自身的同构映射，则称为自同构。

5 群 设G是一个非空集合，并在G内定义了一种代数运算 “ 。”，若满足： ，恒有 1) 封闭性。对任意 2) 结合律。对任意 ，恒有
若加法，恒等元用0表示， 若为乘法，恒等元称为单位元 阿贝尔群(Abelian Group)、可换群、交换群：满足交换律 1) 封闭性。对任意 ，恒有 2) 结合律。对任意 ，恒有 3) G中存在一恒等元e,对任意 ，使 4) 对任意 ，存在a的逆元 ，使

6 环 非空集合R中，若定义了两种代数运算加和乘，且满足： 环＝阿贝尔加群＋乘法半群 相关概念 1) 集合R在加法运算下构成阿贝尔群
2) 乘法有封闭性 3) 乘法结合律成立，且加和乘之间有分配律 环＝阿贝尔加群＋乘法半群 相关概念 有单位元环（乘法有单位元） 交换环（乘法满足交换率） 整环（无零因子环）

7 域 定义：非空集合F，若F中定义了加和乘两种运算，且满足： 域是一个可换的、有单位元、非零元素有逆元的环，且域中一定无零因子。
3) 加法和乘法之间满足分配律 域是一个可换的、有单位元、非零元素有逆元的环，且域中一定无零因子。 元素个数无限的域称为无限域；元素个数有限的域称为有限域，用GF(q)或Fq表示q阶有限域。有限域也称为伽逻华域。

8 子环 定义 判定 例子 若环R中的子集S，在环R中的定义的代数运算也构成环，则称S为R的子环，R为S的扩环
对任何两个元素a, b∈S ， 恒有a-b ∈S； 对任何两个元素a, b∈S， 恒有ab ∈S； 例子 全体整数集合构成一个可换环。以某一整数m的倍数全体构成其中的一个子环。如m=3, 集合{…, -3, 0, 3, …}构成一个子环

9 理想 理想 主理想 非空子集I是交换环R的理想的充要条件是：
对任何两个元素a, b∈I ， 恒有a-b ∈I；Abel加群 对任何两个元素a ∈I, r∈R， 恒有ar=ra ∈I；若I包含了a，则包含了a的一切倍元 I构成一个Abel加群，所以可用它作为一个正规子群，把R中的元素进行分类划分陪集 主理想 若理想中的元素由一个元素的所有倍数及其线性组合生成，则称这个理想为主理想。 在可换环R中，由一个元素a ∈R所生成的理想I(a)={ra + na|r ∈R, n ∈Z}称为环R的一个主理想，称元素a为该主理想的生成元

10 剩余类环 定义 例 设R是可换环，I为R的一个理想，于是R模I构成一个可换环，称它为环R以理想I为模的剩余类环
R=Z，I3={…, -3, 0, +3, …}，R以I划分陪集为 集合 构成一个可换环

11 多项式 多项式 多项式次数 degf(x) 首一多项式 既约多项式 f(x)=fnxn+ fn-1xn-1+…+ f1x+f0
其中 i=0,1,…,n，该多项式称为域Fp上的多项式 多项式次数 degf(x) 系数不为零的x的最高次数称为多项式f(x)的次数 首一多项式 最高次数的系数为1的多项式 既约多项式 设f(x)是次数大于零的多项式，若除常数和常数与本身的乘积以外，再不能被域Fp上的其他多项式整除，则称f(x)为域Fp上的既约多项式 f(x)是否既约与讨论的域有关：f(x)=x2+1在实数域上既约，但在复数域上f(x)=(x+i)(x-i)

12 既约多项式 每一个首一多项式必可分解为首一既约多项式之积，并且当不考虑因式的顺序时，该分解是唯一的
其中，pi(x)为首一既约多项式， 为正整数 d次多项式f(x)不可能有多于d个的一次因式, 至多有d个根 α为之根的充要条件是 (x-α)| f(x) 若p(x)是f(x)的k重既约因式，则p(x)必是f’(x)的k-1重既约因式

13 GCD&LCM GCD (f(x), g(x))：同时除尽f(x)和g(x)的次数最高的首一多项式
LCM [f(x), g(x)]：同时被f(x)和g(x)除尽的次数最低的首一多项式 f(x) g(x)= (f(x), g(x)) [f(x), g(x)] Euclidean算法 (f(x), g(x))=A(x) f(x)＋B(x) g(x)

14 多项式的加法和乘法 设 f(x)=fnxn+ fn-1xn-1+…+ f1x+f0
g(x)=gmxm+ gm-1xm-1+…+ g1x+g0 多项式相等 若m=n，且对所有i, fi=gi, 则f(x)=g(x) 多项式加（若n>m) 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

15 多项式剩余类环 结论 多项式剩余类环 剩余类之间的加法和乘法运算规则
按上述定义的加法和乘法运算，Fp[x]构成一个具有单位元、无零因子的可换环 多项式剩余类环 以一个Fp上的多项式f(x)=fnxn+ fn-1xn-1+…+ f1x+f0为模的剩余类全体构成一个多项式剩余类环 Fp[x]上任一多项式f(x)的一切倍式集合If(x)组成一个理想。以此理想把Fp[x]划分陪集，这些陪集全体就构成了模f(x)的剩余类环 剩余类之间的加法和乘法运算规则

16 Examples GF(2)上的多项式 f(x)=x2+1的剩余类全体为： 对所定义的加法和乘法运算， 构成剩余类环 元素 没有乘法逆元

17 Examples 结论：若n次首一多项式f(x)在域Fp上既约，则f(x)的剩余类环构成一个有pn个元素的有限域
GF(2)上的多项式 f(x)=x2+x+1的剩余类全体为： 对所定义的加法和乘法运算， 构成域 结论：若n次首一多项式f(x)在域Fp上既约，则f(x)的剩余类环构成一个有pn个元素的有限域

18 主理想环与同构 多项式环Fp[x]的一切理想均是主理想
多项式剩余类环Fp[x]/f(x)中的每一个理想都是主理想。且该主理想的生成元必除尽f(x) GF(2)上二次多项式与GF(2)上的三重。它们的元素具有如下的一一对应关系 且在适当定义运算之后具有同样的性质与结构。称具有这种对应关系的两个集合为同构

19 循环群的定义 定义：由一个单独元素的所有幂次所构成的群称为循环群，该元素为循环群的生成元
幂次的含义与在群上所定义的运算有关。若定义加法运算，幂运算为连加运算；若定义乘法运算，则幂运算为连乘。 循环群的生成元不止一个。 凡是循环群必是可换群。 例：模4剩余类全体关于加法运算构成循环群，生成元为1和3。

20 循环群的构造及性质 有限循环群和无限循环群 循环群元素的级 若元素a的所有幂次均不相同(无限循环群)
存在整数 h和k，使得ak=ah，则有a生成的循环群中元素个数有限(有限循环群) 循环群元素的级 若ak=ah，则有ah-k=e，定义使an=e的最小正整数为有限循环群元素a的级。 a0=e, a1, …, an-1均不相同 an=e ，则a的一切幂次生成的元素都在 G(a)={a0=e, a1, …, an-1 }中 可换群G中的每一个元素a都能生成一个循环群。若a为有限级，则生成有限循环群， a的级即为循环群中元素的个数(循环群的阶)

21 有限循环群中级的性质 若a是n级元素，则am=e的充要条件是n|m 若a是n级元素， b是m级元素，且(n,m)=1,则 (ab)的级为nm
若a是n级元素， 则ak的级为n/(k,n) 若a是dk级元素， 则ak为d级元素 n阶循环群中，每个元素的级是群阶数n的因子 单位原根：n阶循环群中，每一个n级元素称为n次单位原根 n阶循环群中有 个单位原根 欧拉函数：0, 1, …, n-1中与n互素的个数 如n=12=3×22，则

22 有限域的乘法结构 域的乘法群必为某一个元素生成的循环群，即q元域中必能找到一个，其阶为q-1。即所有有限域元素都能表示成生成元的幂次的形式，此时的生成元称为本原元。 在GF(q)中，每一个非0元素均满足xq-1=1，即都是方程 xq-1-1=0的根。反之， xq-1-1=0的根必在GF(q)中 GF(q)中必有本原域元素存在 在含有n次单位原根的任意域上，有下述因式分解

23 分圆多项式 为Mobius函数，pi为素数 以GF(q)中彼此不同的d级元素为全部根的首一多项式，称为d级分圆多项式，记为Q(d)(x)
其中 为Mobius函数，pi为素数

24 Mobius反演公式 Mobius反演公式 在分圆多项式的计算中，令

25 Examples 分解GF(2)上的x15-1多项式

26 有限域的加法结构 域的特征 满足ne=0的最小n值为域的特征，这里e为乘法单位元，0为域的零元，n取自正整数 GF(p)的特征为p 每一个域的特征或为素数，或为∞ 域的特征说明了域中加法运算的循环性，而域中元素的级则说明了乘法运算的循环性。 元素的周期 对域中元素a≠0，满足na=0的最小n值为a的周期。（注意对于域而言，在加法上用周期，在乘法上用级） 域中非0元的周期都相同，且与域的特征相等 在p特征域中，域整数全体（形如ne的全体域元素: n=…, -2, -1, 0 ,1, 2, …）构成p阶素子域，它与模p的整数域GF(p)同构

27 有限域加法性质 GP(p)为GF(pm)的基域，GF(pm)为GF(p)的扩域，GF(pm)的特征为p。
如GF(22)的4个元素: 00, 01, 10, 11中的每一个特征均为2；故GF(22)是一个特征为2的域 在特征为p的域中，恒有 其中，a是域中的任一元素 在p特征域中，对任何域元素a, b，恒有 在p特征域中，任一元素的级均不是p的倍数

28 有限域加法性质 若w1, w2, …, wk是p特征域的元素，则对于一切自然数n，恒有
Fermat定理：对GF(pm)中的任何元素w，恒有 任何小于素数p的整数b满足 ，如 p特征域中，元素为域整数的充要条件是满足

29 最小多项式 若 为方程 的根，则GF(pm)中互不相同的m个元素 是f(x)的m个不同的根。这m个根称为方程f(x)的共轭根系
若 为方程 的根，则GF(pm)中互不相同的m个元素 是f(x)的m个不同的根。这m个根称为方程f(x)的共轭根系 能满足pm=1(mod n)的最小整数m，称为p对模n的方次数 系数取自GF(p)的，以w为根的所有首一多项式中，次数最低的称为w的最小多项式m(x)，w的最小多项式的次数m称为w的次数，称w为m次域元素

30 最小多项式 性质 m(x)在GF(p)上不可约 若w也是f(x)的根，则m(x)可整除f(x) 若w取自GF(pm)，则有m(x)可整除
设w是p特征域GF(pm)中的n级元素，而pm=1(mod n)，则w的最小多项式m(x)是m次多项式，且 在GF(pm)域中完全分解m(x)为一次因式之积，所以称GF(pm)为m(x)的分离域或分解域

31 本原多项式 在GF(pm)中，以本原元为根的最小多项式称为该域的本原多项式
GF(pm)的本原多项式的根级数均为pm-1，且本原多项式必为m次多项式 w为最小多项式的根，若w是特征为p的有限域F上的m次域元素，则所有小于m次的多项式f(x)将w代入，得到的集合构成pm阶子域。（以最小多项式为模） 如：GF(2)上f(x)=x3+x+1，以GF(23)上的元素w为根，则GF(2)上小于3次w多项式全体构成23阶子域：0, 1, w, w +1, w 2, w 2 +1, w 2 +w, w 2 +w +1 对于m次元素w，有1, w, w2, …, wm-1线性无关，可作为域空间的基。 可以由GF(p)上的一个m次本原或既约多项式，用它的根w构成的这组基底的线性组合，构造一个GF(pm)有限域

32 互反多项式 定义 性质 设GF(p)上的m次多项式 则 称为互反多项式 例： 若α为f(x)的根，则α-1为f*(x)的根

33 多项式的周期 定义 设f(x) ∈Fp[x], f(0) ≠0（即x !| f(x) ），则f(x)|(xl-1)的最小正整数l，称为f(x)的周期（或指数），记为p(f) 性质 f(x)的周期l是以f(x)为模所构成多项式剩余类环中乘法群内元素 之级 f(x) ∈Fp[x], f(0) ≠0，则f(x)|(xl-1)的充要条件是p(f)|l 多项式(xm-1)|(xn-1)的充要条件是m|n 若f(x)是Fp[x]中m次既约多项式，则f(x)之周期p(f)等于f(x)在GF(pm)中的根的级

34 多项式的周期 性质(cont.) GF(p)上多项式f(x)的标准分解式若为 则f(x)的周期 式中 是≥x的最小整数

35 多项式的周期 Example GF(2)上的多项式 因为 以5级元素为根 以15级元素为根

36 有限域的代数结构 有限域的阶必为其特征（素数）之幂
设f(x)为p阶有限域GF(p)上的一个d次既约多项式，则多项式剩余类集合Fp[x]/f(x)构成pd阶有限域GF(pd) 。即GF(pd)是GF(p)的扩域，且f(x)在GF(pd)内有根 GF(pr)含有子域GF(ps)的充要条件是s|r 若β∈ GF(pr) ，则β∈ GF(ps)中的充要条件是 。特别是在任何域中若 ，则β是0或1 p阶有限域上的每一个d次首一既约多项式，皆能整除 ，只要d|m

37 最小扩域 系数取自GF(p)上的多项式 =所有次数除尽m的GF(p)上的首一既约多项式之积 如：x4-x=x(x+1)(x2+x+1)
若f(x)为GF(p)上的m次既约多项式，且m|d，则任何pd阶有限域必含有f(x)的全部根 若d=m，则m次首一既约多项式f(x)的全部根在GF(pm)中，称GF(pm)为f(x)的包含所有根的最小扩域，称为f(x)的分裂域或分解域 例：GF(2)上的既约多项式 必在GF(24)上完全分裂，但不能在任何中间域GF(22)完全分裂

38 既约多项式的数目 GF(p)上m次既约多项式的数目是 式中 为Mobius函数 例： GF(2)上3次既约多项式的数目 分别为

39 同构 m重、多项式剩余类以及α多项式之间均同构，都可用来表示pm阶有限域

40 因式分解 分解 注意到22=1(mod 3) Q(3)(x)既约 24=1(mod 5) Q(5)(x)既约

41 待定系数法 Q(15)(x)的既约因式必为 x4+Ax3+Bx2+Cx+1 1不是15级元素A+B+C=1
1) A=B=C=1 x4+x3+x2+x+1= Q(5)(x); rejected 2) A、B、C中只有1个为1 B=1 x4+x2+1=(x2+x1+1)2; rejected A=1 x4+x3+1; accepted C=1 x4+x+1; accepted Remark: x4+x3+1， x4+x+1为互反多项式 因此

42 因式分解 均以15级元素为根。因此，若以此多项式作剩余类，就能得到24阶有限域GF(24)。若以 的根α表示，则上的15个非0元素如下所示

43 因式分解 把x9-1分解为GF(2)上的既约因式乘积
找9级元素的最小多项式，注意到26=1(mod 9); 故9级元素的最小多项式的次数为6，因此9级元素必在GF(26)上。设α为GF(26)上的本原域元素α63=1，则(α7)9=1 ， α7为9级元素。因此 故

44 正规基和对偶基 定义 为GF(pm)域的正规基，这里，α是GF(pm)中的本原域元素 α∈GF(qm)，则它在GF(q)上的迹定义为

45 正规基和对偶基 Example: α是f(x)= x3+x2+1的根，则 与GF(pm)的基底 相对应，若
满足，则称GF(pm)的基底 是B的对偶基

46 Example 若α是本原多项式f(x)= x3+x2+1的根，则 自然基 自然基的对偶基 正规基

47 Example (Continued)