离散数学 教学课件 作者 赵一鸣 阚海斌 吴永辉 dshu16.ppt

《离散数学 教学课件 作者 赵一鸣 阚海斌 吴永辉 dshu16.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、引理15.5：[G;*]为交换群,aG是其中阶最大元,设其阶为n。则任一xG的阶可整除n。定理15.16:GF(pm)中非零元全体关于乘法构成循环群。关键证明存在元素，其阶为pm－1。找元素，阶最大的。定义15.10:循环群[GF(pm)*;*]之生成元称为有限域GF(pm)的本原元。GF((pm))是本原元,则GF((pm))中元素可表示为:GF((pm))={0,0=1,,2,,pm-2}例:找出GF(32)的所有本原元。不可约多项式x2+1+1,+2,2+1,2+2都是本原元+1是本原元,则其他元素2,,+2,2,2+1,2+2

2、怎样表示成+1的幂次?二、本原多项式定义15.11:设g(x)Zp[x]是m次不可约多项式,当k=pm-1时g(x)

3、(xk-1),当k

4、15.16:f(x)不可约,f(x)与g(x)有公共零点,则f(x)

5、g(x)例:GF(22)≌Z2[x]/(x2+x+1),证明x2+x+1是Z2上的本原多项式。设是Z2[x]上的多项式(x2+x+1)的根,请将下式化简为的幂次。(2+)*(2+1)-1+-2+例:GF(24)≌Z2[x]/(x4+x+1),证明x4+x+1是Z2上的本原多项式。已知为GF(pn)上的本原元，怎样求出GF(pn)上的所有本原元？GF*(pn)中的每个元素可表示为的幂次形式k。由习题13.19知，k的阶为pn-1当且仅当(k,pn-1)=1，即k为本原元当且仅当(k

6、,pn-1)=1。因此我们就可在,2,pn-1中找出所有的本原元。已知Zp上的一个n次本原多项式f(x),怎样求出Zp上所有的n次本原多项式?1.费尔马小定理:设p为素数,a为非零整数,且(a,p)=1,则ap-11modp证明:对任意与p互素的非零整数a,有[a]pZp*,因为元素的阶是群的阶的因子,所以[a]p-1=1,即ap-1=1modp,2.(x)=xp是GF(pn)的自同构映射.证明:满足同态等式一对一满射:设为生成元,对任意的GF(pn),有=k,取x=kpn-1,则(x)=(kpn-1)p=(kpn)=(pn)k=(pn

7、-1)k=k3.设为本原多项式f(x)的根,则,p,p2,,pn-1是本原元,且是f(x)的根.证明:(1)pi是本原元先证明(pi,pn-1)=1然后由习题13.19得:pi的阶是pn-1所以pi是本原元(2)pi是f(x)的根结论:1.为本原多项式f(x)的根,则有f(x)=(x-)(x-p)(x-p2)(x-pn-1)2.已知Zp上的一个n次本原多项式f(x),求所有n次本原多项式的方法是:(1)先求出f(x)的一个根,即本原元,然后求出GF(pn)中的所有本原元,(2)根据求出的本原元按结论1中的方法构造其他本原多项式.3.凡

8、不可约多项式若有一个根是本原元,则它的所有根都是本原元,即,它一定是本原多项式.如何判别一个多项式不可约，并没有一个行之有效的方法1.在无限数域上的不可约多项式问题复数域上的任何多项式都是可约的。实数域上任何多项式，根据复根共轭的性质，知道实数域上只有2次不可约多项式。有理数域，存在任意次不可约多项式。定理1：若n次整系数多项式f(x)∈Z[x]在有理数域Q上可约，则f(x)在整数环Z上一定可约。定理2(艾森斯坦(Eisenstein)判别法)：设f(x)=a0+a1x+…+anxn是整系数多项式，若能找到一个素数p，使得(1)p不能整除an；(2)p

9、a0,a1,┅,a

10、n-1；(3)p2不能整除a0；那么，f(x)在有理数域上不可约。艾森斯坦判别法是充分条件，不满足定理2的多项式，不一定就可约。如x2+3x+2和x2+1，都不满足定理2条件，前者在有理数域上可约，后者不可约。2.有限域上的不可约多项式有限域上的不可约多项式，最直观的就是将域上所有n次多项式按次数列成表，次数小的在前面，大的在后，次数相等的按某种规定排列先后，排在最前面的多项式就是不可约的，把它圈出来，再把该多项式倍式的多项式从表中划去。剩下没有圈和划去的多项式中排在最前的就是不可约的，重复这一过程即可，但当n适当大时，工作量