引理15.5:[G;*为交换群,a∈G是其中阶最大 元,设其阶为n则任一x∈G的阶可整除n 定理15.16:GF(p)中非零元全体关于乘法构 成循环群。 关键证明存在元素,其阶为p-1。 找元素,阶最大的
引理15.5：[G;*]为交换群,aG是其中阶最大 元,设其阶为n。则任一xG的阶可整除n。 定理15.16:GF(pm)中非零元全体关于乘法构 成循环群。 关键证明存在元素，其阶为p m－1。 找元素，阶最大的
定义15.10:循环群GF(p);之生成元称 为有限域GF(p)的本原元。 β∈GF(pP)是本原元,则GF(p)中元素 可表示为: GF(p)={0,80=1,B,B2,,Bp2 例:找出GF(32)的所有本原元 不可约多项式x2+1 α+1,a+2,2a+1,2a+2都是本原元
定义15.10:循环群[GF(pm) * ;*]之生成元称 为有限域GF(pm)的本原元。 GF((pm))是本原元, 则GF((pm))中元素 可表示为: GF((pm))={0, 0=1,, 2 ,, pm-2 } 例:找出GF(32 )的所有本原元。 不可约多项式x 2+1 +1, +2, 2+1, 2+2都是本原元
a+1是本原元,则其他元素2,a,a+2,2a, 2a+1,2a+2怎样表示成a+1的幂次? 二、本原多项式 定义151:设g(x)∈Znx是m次不可约多 项式当k=p-1时g(x)(xk1),当kpm1时 g(x)不能整除(xk1,称g(x)为Z上的本原 多项式
+1是本原元,则其他元素2,, +2,2, 2+1,2+2怎样表示成+1的幂次? 二、本原多项式 定义15.11:设g(x)Zp [x]是m次不可约多 项式,当k=pm-1时g(x)|(xk-1),当k<pm-1时 g(x)不能整除(x k-1),称g(x)为Zp上的本原 多项式
定理1517:g(x)∈Zx是不可约的m次多 项式,它是本原多项式,当且仅当g(x)的所 有根x都是Znx/(g(x)=GF(p)的本原元。 (1)g(x)是不可约的m次多项式,所有根都是 Z2lx(g(x)=GF()的本原元则是本原多项 式 (g(x)x是g(x)的根则阶为p1 (2)g(x)是本原多项式 g(x)与x-1有公共零点 习题15.16:f(x)不可约,fx)与g(x)有公共零点,则 f(x)lg(x)
定理15.17:g(x)Zp [x]是不可约的m次多 项式,它是本原多项式,当且仅当g(x)的所 有根x都是Zp [x]/(g(x))=GF(pm)的本原元。 ( 1 ) g(x)是不可约的 m次多项式 , 所有根都是 Zp [x]/(g(x))=GF(pm)的本原元,则是本原多项 式 (g(x))+x是g(x)的根,则阶为p m-1 (2)g(x)是本原多项式 g(x)与x t -1有公共零点 习题15.16:f(x)不可约,f(x)与g(x)有公共零点,则 f(x)|g(x)
例:GF(2)≌Z2x]/(x2+x+1),证明x2+x+1是 Z2上的本原多项式。 设α是Z2x上的多项式(x2+x+1)的根,请 将下式化简为的幂次 (a2+a)*(a2+1)1+a-2+o 例:GF(24)≌Z2x]/(x4x+1),证明x4x+1是 Z2上的本原多项式
例:GF(2 2 )≌Z2 [x]/(x2+x+1),证明x 2+x+1是 Z2上的本原多项式。 设是Z2 [x]上的多项式( x 2+x+1)的根,请 将下式化简为的幂次。 (2+)*(2+1)-1+-2+ 例:GF(2 4 )≌Z2 [x]/(x4+x+1),证明x 4+x+1是 Z2上的本原多项式
已知α为GF(p上的本原元,怎样求出GF(p) 上的所有本原元? GF(p)中的每个元素可表示为的幂次形式 由习题1319知,∝的阶为p2-1当且仅当(k, pn-1)=1,即α为本原元当且仅当(k,p-1)=1 因此我们就可在a,x2,Cp1中找出所有的本 原元
已知为GF(pn )上的本原元，怎样求出GF(pn ) 上的所有本原元？ GF*(pn )中的每个元素可表示为的幂次形式 k 。 由习题13.19知，k的阶为p n -1当且仅当(k, p n -1)=1，即k为本原元当且仅当(k, pn -1)=1。 因此我们就可在,2 ,p n-1中找出所有的本 原元
已知Zn上的一个n次本原多项式fx),怎样 求出Z上所有的m次本原多项式? 1费尔马小定理: 设p为素数,a为非零整数,且(a,p)=1,则 ap-=l mod p 证明对任意与p互素的非零整数a 有al∈Z, 因为元素的阶是群的阶的因子, 所以[ap=1, 即apl=1modp
已知Zp上的一个n次本原多项式f(x),怎样 求出Zp上所有的n次本原多项式? 1.费尔马小定理: 设p为素数,a为非零整数,且(a,p)=1,则 a p-11 mod p 证明:对任意与p互素的非零整数a, 有[a]pZp * , 因为元素的阶是群的阶的因子, 所以[a]p-1=1, 即a p-1=1modp
2q(x)=x?是GF(P)的自同构映射 证明:满足同态等式 对 满射设为生成元对任意的B∈GF(p), 有β=取 X-O Ai(x =(akp)P=(akp)=(aP) c c
2.(x)=xp是GF(pn )的自同构映射. 证明:满足同态等式 一对一 满射:设为生成元,对任意的GF(pn ), 有=k ,取x=kpn-1 , 则(x)=(kpn-1 ) p = (kpn )= (p n ) k =(p n -1 ) k = k
3设a为本原多项式fx根则a,a,a? ,aP是本原元,且是x)的根 证明:(1)op是本原元 先证明(p,p-1)=1 然后由习题13,19得:P的阶是p1 所以a是本原元 (2)0xp是x)的根
3.设为本原多项式f(x)的根,则,p ,p2 , ,p n-1是本原元,且是f(x)的根. 证明:(1)pi是本原元 先证明(p i ,pn-1)=1 然后由习题13.19得:pi的阶是p n-1 所以pi是本原元 (2)p i是f(x)的根
结论: 1.a为本原多项式x)的根则有 f(x=(x-C)(x-aLP)(x-aP)(x-aP) 2已知Z上的一个m次本原多项式敢x)求 所有n次本原多项式的方法是 (1)先求出x)的一个根,即本原元a,然后 求出GF(p)中的所有本原元, (2)根据求出的本原元按结论1中的方法 构造其他本原多项式 3凡不可约多项式若有一个根是本原元, 则它的所有根都是本原元,即它一定是本 原多项式
结论: 1. 为本原多项式f(x)的根,则有 f(x)=(x-)(x-p )(x-p 2 )(x-p n-1 ) 2.已知Zp上的一个n次本原多项式f(x),求 所有n次本原多项式的方法是: (1)先求出f(x)的一个根,即本原元,然后 求出GF(pn )中的所有本原元, (2)根据求出的本原元按结论1中的方法 构造其他本原多项式. 3.凡不可约多项式若有一个根是本原元, 则它的所有根都是本原元,即,它一定是本 原多项式