《数论与有限域-第六章课件.ppt》由会员分享，可在线阅读，更多相关《数论与有限域-第六章课件.ppt（67页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第六章第六章有限域的抽象性有限域的抽象性质第一第一节 有限域的加法有限域的加法结构构 一、域的特征一、域的特征 二、有限域二、有限域F F中的元素个数中的元素个数 一、域的特征一、域的特征设e为有有限限域域F中中的的乘乘法法单位位元元。定定义F中中的的序序列列u0,u1,u2,如下如下u0=0,un=un1+e,其中其中n=1,2,.则易知易知 n Z，有，有un=ne，于是，于是在此序列中，在此序列中，m和和n，有，有um+n=(m+n)e=me+ne=um+un且且umn=(mn)e=(mn)e2=mene=umun。由于由于F是有限域是有限域，因而序列因而序列u0,u1,u2,中的元素中
2、的元素不可能不可能都不相同都不相同，故可，故可设存在整数存在整数c，使得，使得u0=0,u1,u2,uk+c1互不相同且互不相同且uk+c=uk。又又uk+cuk=uc，即即uc=ce=0。因而。因而我我们找到了一个整数找到了一个整数c，使得，使得ce=0。一般地。一般地 一、域的特征一、域的特征定理定理6.1.1若若F是有限域，是有限域，则F的特征的特征c必定必定为素数。素数。证明明：假假设相相反反，设正正整整数数c=ab，其其中中1ac，1bc，则由由上上述述有有限限域域F中中的的序序列列u0,u1,u2,所所具具有有的的性性质知知uc=uaub。但但uc=0，而而ua与与ub均均不不为0
3、，如如此此与与域域中中无无零零因因子子的的性性质相矛盾，因而相矛盾，因而c必定必定为素数。素数。在在以以下下的的叙叙述述中中，记有有限限域域的的特特征征为字字母母p，则易易知知序序列列u0,u1,u2,中第一个出中第一个出现重复的元素重复的元素是是up=0，进而而u0,u1,u2,up1互不相同。互不相同。二、有限域二、有限域F F中的元素个数中的元素个数定定理理6.1.2有有限限域域F中中的的元元素素个个数数q必必定定是是某某个个素素数数p的的幂次，即次，即q=pm。证明明：首首先先，容容易易验证域域F的的子子集集u0,u1,u2,up1构构成了成了F的一个子域，的一个子域，记为Fp。若若F
4、=Fp，则q=p，结论得得证。否否则设1 FFp，则 a,b Fp，在在F中中都都可可以以对应地地找找到到一一个个元元素素a1+b，显然然在在F中中共共有有p2个个元元素素具具有有这样的的形形式式，因因而而若若域域F中中元元素素的的数数目目q=p2，则定定理理得得证。二、有限域二、有限域F F中的元素个数中的元素个数否否则在在F中中选择不不具具有有形形式式a1+b的的元元素素2，则 a,b,c Fp，在在F中中都都可可以以对应地地找找到到一一个个元元素素a2+b1+c，显然然在在F中中共共有有p3个个元元素素具具有有此此形形式式，因因而而若若域域F中元素的数目中元素的数目q=p3，则定理得定理
5、得证。否否则，我我们在在F中中选择不不具具有有形形式式a2+b1+c的的元元素素3，。最最终，在在F中中可可以以选定定一一组元元素素1,2,m1，使使得得F中中 的的 每每 个个 元元 素素 都都 有有 唯唯 一一 的的 表表 达达 式式：=a1+a21+a32+am1m1，其其中中ai Fp，i=1,2,m1。由由于于每每个个ai有有p个个可可能能的的取取值，因因而而F中中恰恰有有pm个元素。定理得个元素。定理得证 二、有限域二、有限域F F中的元素个数中的元素个数通通过定定理理6.1.2，对有有限限域域F的的加加法法结构构我我们可可以以得得到到如如下下认识：有有限限域域F中中的的元元素素可
6、可以以看看做做是是域域Fp中中元元素素构构成成的的m元元组，且且(a1,a2,am)+(b1,b2,bm)=(a1b1,a2+b2,am+bm)接下来，我接下来，我们来研究域来研究域F的乘法的乘法结构。构。一、元素的一、元素的阶以以下下设F为有有限限域域，F*为有有限限域域F中中的的所所有有非非零零元元素素构构成成的的集集合合，F*，考考察察由由的的各各个个幂次次所所构构成成的的序序列列e,2,n,的性的性质。首首先先由由域域F对乘乘法法运运算算的的封封闭性性，知知 i，i F，又又F是是有有限限域域，因因而而序序列列e,2,n,中中必必然然会会出出现重复。重复。设e,2,k+t1互不相同且互
7、不相同且k=k+t，则k=0；否否则若若k0，则由由k=k+t得到得到k1=k+t1，这与与e,2,k+t1互不相同相矛盾，互不相同相矛盾，进而而t=e。一般地一般地一、元素的一、元素的阶定定理理6.2.1设有有限限域域F具具有有q个个元元素素，F*，若若的的阶为t，则t|(q1)。证明明：由由域域的的定定义，F*构构成成了了乘乘法法群群，由由于于的的阶为t，即即t=e，因因而而e,2,t1构构成成了了F*的的子子群群。拉拉格格朗朗日日定定理理子子群群中中的的元元素素个个数数一一定定会会是是整整个个群群的的元元素素个个数数的的因因子子，因而因而t|(q1)。一、元素的一、元素的阶从从而而r(x
8、)是是Fx中中的的常常数数多多项式式，也也即即域域F中中的的一一个个元元素素。由于由于p()=0，因而，因而p()=q()()+r()=0，即，即r()=0，而而r(x)是域是域F中的一个元素，因而中的一个元素，因而r(x)=0，于是，于是p(x)=q(x)(x)，并并且且方方程程p(x)=0的的任任意意一一个个不不等等于于的的根根都都是是方方程程q(x)=0的根。的根。但但是是q(x)的的次次数数为m1，由由归纳假假设方方程程q(x)=0至至多多有有m1个根，因而方程个根，因而方程p(x)=0至多有至多有m个根。个根。一、元素的一、元素的阶例例6.2.1设Z8为整数模整数模8的剩余的剩余类环
9、，即，即定定义了模了模8的加法和乘法运算的集合的加法和乘法运算的集合0,1,2,7。在在这个个环中中，通通过验证我我们会会发现多多项式式方方程程x21=0有有4个不同的根个不同的根x=1,3,5,7。即即我我们竟竟然然得得到到了了一一个个有有4个个根根的的二二次次方方程程，这似似乎乎与与我我们给出出的的引引理理6.2.1矛矛盾盾。但但是是需需要要注注意意的的是是Z8中中有有零零因子因子2和和4，因而不是域，故并不矛盾。，因而不是域，故并不矛盾。一、元素的一、元素的阶推推论6.2.1 若若ord()=t，则每每个个满足足方方程程xt=e的的域域F中中的的元元素都必定是素都必定是的的幂。证明明：若
10、：若ord()=t，即，即t=e，则(i)te=(t)ie=0，即即t个个元元素素e,2,t1是是方方程程xte=0的的t个个不不同同的的根根，而而由引理由引理6.2.1该方程不会再有其它的根！即方程不会再有其它的根！即每个每个满足方程足方程xt=e的域的域F中的元素都必定是中的元素都必定是的的幂。但但是是正正如如下下面面的的引引理理6.2.2所所述述的的，并并不不是是的的每每个个幂次次都都有有阶t。一、元素的一、元素的阶引理引理6.2.2若若ord()=t，则ord(i)=t/gcd(i,t)。证明明：首先，易知：首先，易知 0，有，有s=e当且当且仅当当ord()|s。其次，其次，设d=g
11、cd(i,t)，则i(t/d)=t(i/d)=(t)(i/d)=e。因而。因而ord(i)|(t/d)。另另设s=ord(i)，则is=(i)s=e，而而ord()=t，因因而而t|is。由由于于d=gcd(i,t)，因而存在某整数，因而存在某整数a和和b，使得，使得ia+tb=d。于是于是ias+tbs=ds。则 由由 t|is，有有 t|ds，即即(t/d)|s，因因 而而(t/d)|ord(i)。结 合合ord(i)|(t/d)，就得到，就得到ord(i)=t/d，也即，也即ord(i)=t/gcd(i,t)。一、元素的一、元素的阶例例6.2.2设域域F中中的的元元素素的的阶ord()=
12、8，则利利用用引引理理6.2.2可以可以计算算i，i=0,1,7的的阶的的结果如下表：果如下表：表表61 域域F中各元素中各元素阶列表列表 igcd(i,8)i081118224318442518624718表表61 中有：中有：4个个8阶的元素，的元素，2个个4阶的元素，的元素，1个个2阶的元素，的元素，以及以及1个个1阶的元素；的元素；一、元素的一、元素的阶到到此此，对于于有有q个个元元素素的的有有限限域域F的的元元素素的的阶我我们有有这样的的认识：1.给定正整数定正整数t，若，若t(q1)，则在域在域F中不存在中不存在t阶元素；元素；2.若若t|(q1)，则在在域域F中中或或者者没没有有
13、t阶元元素素，或或者者恰恰有有(t)个个t阶元素。元素。3.接接下下来来我我们证明明若若t确确实整整除除q1，则在在域域F中中将将总是是存存在在有有(t)个个t阶元元素素。在在给出出具具体体证明明之之前前，再再来来看看另外一个例子。另外一个例子。一、元素的一、元素的阶例例6.2.3设q=9，则q1=8，进而而t的可能取的可能取值为1，2，4，8。又又对于于t的每一个可能取的每一个可能取值，t阶元素的个数或者元素的个数或者为0或者或者为(t)个。个。由欧拉函数的性由欧拉函数的性质，计算得到算得到t和和(t)的取的取值如下表：如下表：t(t)11214284注：注：(t)列的和列的和为8，与域，与
14、域F中的非零中的非零元素的个数相同。元素的个数相同。一、元素的一、元素的阶接下来若接下来若设集合集合Sn中的所有分数都已中的所有分数都已进行了行了约简，则集合集合Sn中的每一个分数的分母中的每一个分数的分母d是是n的因子，的因子，其分子其分子e是与是与n相相对互素且介于区互素且介于区间1ed的整数。的整数。反之，若反之，若d是是n的正因子，的正因子，1ed，且，且(e,d)=1，则分数分数e/d必是集合必是集合Sn中某个分数的中某个分数的约简形式。形式。进而而，对于于n的的所所有有因因子子d，Sn将将会会分分解解为若若干干不不相相交交的的集合集合Td的并集，的并集，即即 ，进而而 。同同时由于
15、由于|Sn|=n，|Td|=(d)。因而。因而结论得得证。一、元素的一、元素的阶例例6.2.4计算算(35)。解解：按按照照欧欧拉拉函函数数的的定定义，可可以以在在1，2，3，35中中逐个逐个测试其是否与其是否与35相相对互素。互素。然而，由定理然而，由定理6.2.3应有有(1)+(5)+(7)+(35)=35，同同时，(1)=1，(5)=4，(7)=6，因而因而(35)=35146=24。一、元素的一、元素的阶推推论6.2.2 在在每每个个有有限限域域中中，都都至至少少存存在在一一个个（事事实上上恰恰有有(q1)个个）q1阶元元素素。因因而而任意有限域的乘法群都是循任意有限域的乘法群都是循环
16、群。群。二、本原元二、本原元 定定义6.2.1称称有有限限域域F中中阶为q1的的元元素素，即即循循环群群F*=F0的生成元，的生成元，为本原元。本原元。例例6.2.5给出域出域F=Z5以及域以及域F=Z7中的本原元。中的本原元。解解：首首先先由由上上节的的定定理理6.2.4，域域F=Z5中中恰恰有有(4)，即即2个个本本原原元元，而而域域F=Z7中中恰恰有有(6)，也也即即2个个本本原原元元。下下面面给出具体地出具体地寻找找过程。程。域域F=Z5中的元素中的元素为0,1,2,3,4，其中，其中2的的幂次依次次依次为20=1，21=2，22=4，23=3，24=1，因而，因而2的的阶为4，而，而
17、3的的阶为4/gcd(4,3)=4，4的的阶为4/gcd(4,2)=2，因而因而2与与3是域是域Z5中的本原元。中的本原元。二、本原元二、本原元 例例6.2.5给出域出域F=Z5以及域以及域F=Z7中的本原元。中的本原元。解解：域域F=Z7中中的的元元素素为0,1,2,3,4,5,6，其其中中2的的幂次次为20=1，21=2，22=4，23=1，因而因而2以及其各个以及其各个幂次均不是域次均不是域Z7中的本原元。中的本原元。由由于于1,2,4都都不不是是本本原原元元，下下面面我我们检验3。3的的各各个个幂次依次次依次为30=1，31=3，32=2，33=6，34=4，35=5，36=1，因因
18、而而 3的的 阶 为 6，而而 5的的 阶 为 6/gcd(6,5)=6，6的的 阶 为6/gcd(6,3)=2，因而因而3与与5是域是域Z7中的本原元。中的本原元。二、本原元二、本原元 注意，在注意，在这个算法中：个算法中：由由于于ord(i)=ti，方方程程的的所所有有解解都都是是i的的幂次次，因因而而的的阶s不不会会是是ti的的因因子子。进而而lcm(ti,s)将将会会是是ti的的一个倍数，且会一个倍数，且会严格大于格大于ti。在在第第四四步步中中，找找到到满足足条条件件d|m，e|n，gcd(d,e)=1且且de=lcm(m,n)的的两两个个整整数数m与与n是是可可能能的的。例例如如，
19、m=12，n=18时，可以取，可以取d=4，e=9。在在第第四四步步中中，元元素素的的阶为ti/gcd(ti,ti/d)=d，的的阶为s/gcd(s,s/e)=e。于于是是这两两个个元元素素的的乘乘积的的阶为de=lcm(ti,s)。因因而而在在第第四四步步中中得得到到的的新新的的元元素素i+1的的阶ti+1恰恰好好是是ord(i)的的一一个个倍倍数数，因因而而这个个算算法法最最终必必定会定会终止于一个本原元。止于一个本原元。二、本原元二、本原元 例例6.2.6利利用用多多项式式f(x)=x3+2x+1构构造造一一个个有有限限域域，并并找找出出域中的本原元。域中的本原元。解解：这里里只只给出出
20、了了构构造造域域的的多多项式式，并并未未给出出构构造造域域所所需需的的欧欧氏氏环，因因而而可可以以任任意意选一一个个欧欧氏氏环，只只要要保保证f(x)为此域中的不可此域中的不可约多多项式即可。式即可。注意到在注意到在F3中中f(0)=1，f(1)=f(2)=2，因而，因而该多多项式是式是F3x中的一个不可中的一个不可约多多项式，式，以此可以构造一个具有以此可以构造一个具有27个元素的有限域个元素的有限域F。域域F中中的的元元素素都都可可以以看看做做是是三三维向向量量(a,b,c)，其其中中a,b,c F3=0,1,2。二、本原元二、本原元 在域在域F中注意到中注意到x3x+2(mod x3+2
21、x+1)，x4x2+2x(mod x3+2x+1)，因而可定因而可定义域域F中的加法与乘法运算如下：中的加法与乘法运算如下：(a1,b1,c1)+(a2,b2,c2)=(a1+a2,b1+b2,c1+c2)。(a1,b1,c1)(a2,b2,c2)=(a1a2+a2c1+a1c2+b2b1,2a1a2+a2b1+a1b2+b1c2+b2c1,2a2b1+a1b2+c1c2)接下来利用高斯算法接下来利用高斯算法寻找找这个域中的本原元。个域中的本原元。二、本原元二、本原元 首首先先取取1=(0,1,0)=x，为了了计算算1的的阶，先先来来计算算x的的各各个个幂次次对f(x)取模的取模的结果果x01
22、(mod x3+2x+1),x1x(mod x3+2x+1),x2x2(mod x3+2x+1)x3x+2(mod x3+2x+1)，x4x2+2x(mod x3+2x+1)，x5x3+2x22x2+x+2(mod x3+2x+1),x62x3+x2+2xx2+x+1(mod x3+2x+1)x7x3+x2+xx2+2x+2(mod x3+2x+1),x8x3+2x2+2x2x2+2(mod x3+2x+1)二、本原元二、本原元 x92x3+2xx+1(mod x3+2x+1),x10 x2+x(mod x3+2x+1)x11x3+x2x2+x+2(mod x3+2x+1),x12x3+x2+
23、2xx2+2(mod x3+2x+1)x13x3+2x2(mod x3+2x+1),x142x(mod x3+2x+1)x152x2(mod x3+2x+1),x162x32x+1(mod x3+2x+1)x172x2+x(mod x3+2x+1),x182x3+x2x2+2x+1(mod x3+2x+1)二、本原元二、本原元 x19x3+2x2+x2x2+2x+2(mod x3+2x+1),x202x3+2x2+2x2x2+x+1(mod x3+2x+1)x212x3+x2+xx2+1(mod x3+2x+1),x22x3+x2x+2(mod x3+2x+1)x232x2+2x(mod x3
24、+2x+1),x242x3+2x22x2+2x+1(mod x3+2x+1)x252x3+2x2+x2x2+1(mod x3+2x+1),x262x3+x1(mod x3+2x+1)因而因而1的的阶为26，即在高斯算法中有，即在高斯算法中有t1=26。由于由于t1=q1=26，算法停止；，算法停止；1就是就是F中的本原元。中的本原元。二、本原元二、本原元 例例6.2.7利利用用多多项式式f(x)=x22构构造造一一个个有有限限域域，并并找找出出这个域中的本原元。个域中的本原元。解解：这里里只只给出出了了构构造造域域的的多多项式式，并并未未给出出构构造造域域所所需需的的欧欧氏氏环，因因而而需需要
25、要选择一一个个欧欧氏氏环，并并保保证f(x)为此域中的不可此域中的不可约多多项式。式。注意到在注意到在F3中中f(0)=1，f(1)=f(2)=2，因而，因而该多多项式是式是F3x中的一个不可中的一个不可约多多项式，式，以此可以构造一个具有以此可以构造一个具有9个元素的有限域个元素的有限域F。域域F中中的的元元素素都都可可以以看看做做是是二二维向向量量(a,b)，其其中中a,b F3=0,1,2。二、本原元二、本原元 在在域域F中中注注意意到到x22(mod x22)，因因而而可可定定义域域F中中的的加加法与乘法运算如下：法与乘法运算如下：(a1,b1)+(a2,b2)=(a1+a2,b1+b
26、2)。(a1,b1)(a2,b2)=(a1b2+a2b1,b1b2+2a1a2)接下来利用高斯算法接下来利用高斯算法寻找找这个域中的本原元。个域中的本原元。首首 先先 取取 1=(1,0)=x，为 了了 计 算算 1的的 阶，先先 来来 计 算算1=(1,0)=x的各个的各个幂次次对f(x)取模的取模的结果果x01(mod x22),x1x(mod x22),x22(mod x22)x32x(mod x22)，x42x21(mod x22)，二、本原元二、本原元 因而因而1=(1,0)=x的的阶为4，即在高斯算法中有即在高斯算法中有t1=4。由于由于t1q1=8，因而因而1不是本原元，不是本原
27、元，接着接着转至第至第3步，需要步，需要选择一个不是一个不是1的的幂次的元素次的元素，例如可以例如可以选=(1,2)=x+2，则2=(x+2)2x(modx22)=(1,0)，以二以二维向量表示向量表示为表表63 1=(1,0)=x各个各个幂次的向量表示次的向量表示 i1i0(0,1)1(1,0)2(0,2)3(2,0)4(0,1)二、本原元二、本原元 类似地可以得到似地可以得到=(1,2)=x+2的的各各个个幂次次对f(x)取取模模的的结果果的的向向量量表示表示因而因而的的阶s=8=q1，则令令2=，算法停止；算法停止；2就是就是F中的本原元。中的本原元。ii0(0,1)1(1,2)2(1,
28、0)3(2,2)4(0,2)5(2,1)6(2,0)7(1,1)8(0,1)表表64 =(1,2)=x+2的各个的各个幂次的向量表示次的向量表示二、本原元二、本原元 例例6.2.8 在在上上例例中中，由由于于f(x)=x22在在F5中中也也没没有有2的的平平方方根根，因因而而该多多项式式也也是是F5x中中的的一一个个不不可可约多多项式式，由由此也可以构造一个具有此也可以构造一个具有25个元素的有限域个元素的有限域F如下。如下。首首先先域域F中中的的元元素素都都可可以以看看做做是是二二维向向量量(a,b)，其其中中a,b F5=0,1,2,3,4。在在域域F中中注注意意到到x22(mod x22
29、)，因因而而可可定定义域域F中中的的加加法与乘法运算如下：法与乘法运算如下：(a1,b1)+(a2,b2)=(a1+a2,b1+b2)。(a1,b1)+(a2,b2)=(a1b2+a2b1,b1b2+2a1a2)接下来利用高斯算法接下来利用高斯算法寻找找这个域中的本原元。个域中的本原元。二、本原元二、本原元 首首 先先 取取 1=(1,0)=x，计 算算 得得 到到1=(1,0)=x的的各各个个幂次次对f(x)取取模模的的结果的向量表示果的向量表示 因因而而1的的阶为8，即即在在高高斯斯算算法法中中t1=8。由由于于t1q1=24，因因而而1不不是是本本原原元元，接接着着转至至第第3步步，需需
30、要要选择一一个个不不是是1的的幂次次的的元元素素，例如可以例如可以选=(1,1)=x+1，则 2=(x+1)2 2x+3(modx22)=(2,3)，类似似地地可可以以得得到到的的各各个个幂次次对f(x)取模的取模的结果的向量表示如下果的向量表示如下 i1i0(0,1)1(1,0)2(0,2)3(2,0)4(0,4)5(4,0)6(0,3)7(3,0)8(0,1)表表65 1=(1,0)=x的的各个各个幂次的向量表示次的向量表示二、本原元二、本原元 因而因而的的阶为12，进而而1=(1,0)，=(1,1)，t1=8，s=12，转到第四步。到第四步。由由 于于 lcm(8,12)=24，满 足足
31、 条条 件件gcd(d,e)=1且且de=lcm(t1,s)的的t1=8的的因因子子d，s=12的的因因子子e，只只有有d=8，e=3，因而，因而2=18/812/3=14=1(21+2)=212+21=2x2+2x2x+4(mod x22)且且2的的阶为lcm(8,12)=24。因因而而t2=24，返返回回第第二二步步，算算法法停停止止；2x+4即即为F中的本原元。中的本原元。ii0(0,1)1(1,1)2(2,3)3(0,2)4(2,2)5(4,1)6(0,4)7(4,4)8(3,2)9(0,3)10(3,3)11(1,4)12(0,1)三、最小多三、最小多项式与本原多式与本原多项式式设F
32、是是有有pm个个元元素素的的有有限限域域，则由由前前面面的的讨论F可可以以看看做做是是Fp上的一个上的一个m维向量空向量空间。接下来接下来 F，考察，考察F中的中的m+1个元素个元素1,2,m。由由于于F在在Fp上上的的维数数为m，因因而而这m+1个个元元素素在在Fp上上必必然然是是线性性相相关关的的，即即存存在在不不全全为零零的的元元素素a0,a1,am，使得，使得a0+a1+a22+amm=0。即即是多是多项式方程式方程a(x)=a0+a1x+a2x2+amxm=0的根。的根。当当然然，也也可可以以满足足其其它它多多项式式方方程程，因因而而可可以以定定义S()为所有所有这样的多的多项式构成
33、的集合，即式构成的集合，即S()=f(x)Fpx:f()=0。三、最小多三、最小多项式与本原多式与本原多项式式设p(x)为集集合合S()中中次次数数最最低低的的非非零零多多项式式，f(x)为集集合合S()中中的的任任意意多多项式式。则由由带余余数数除除法法，可可以以找找到到多多项式式q(x)与与r(x)，使得，使得f(x)=q(x)p(x)+r(x)，deg(r)deg(p)但但是是由由于于f()=p()=0，因因而而r()=0。这与与deg(p)的的最最小小性性相相矛矛盾盾，因因而而r(x)=0，进而而集集合合S()中中的的任任意意多多项式式f(x)都是都是p(x)的倍式。的倍式。称称集集合
34、合S()中中次次数数最最低低的的这个个多多项式式p(x)为域域F中中以以为根根的的最小多最小多项式式。若要求。若要求p(x)是首一多是首一多项式，式，则这样的的p(x)是唯一的，并且是不可是唯一的，并且是不可约多多项式式。这是是由由于于，若若p(x)=a(x)b(x)，则由由于于p()=0，必必然然会会得得到到a()=0或或b()=0，这与与deg(p)的最小性相矛盾。的最小性相矛盾。三、最小多三、最小多项式与本原多式与本原多项式式定定理理6.2.5 设F是是有有pm个个元元素素的的有有限限域域，则 F，若若Fpx中存在唯一的首一多中存在唯一的首一多项式式p(x)，使得，使得i.p()=0，i
35、i.deg(p)m，iii.若若f(x)为Fp(x)中中另另外外一一个个以以为根根的的多多项式式，则p(x)|f(x)。则称称p(x)为的的相相对于于F的的子子域域Fp的的最最小小多多项式式，若若为本本原原元元，则称称其其所所对应的的最最小小多多项式式为本本原原多多项式。式。三、最小多三、最小多项式与本原多式与本原多项式式例例6.2.9计算例算例6.2.7所所给域中某些个元素的最小多域中某些个元素的最小多项式。式。解解：考：考虑元素元素(1,0)的的幂次，次，这里里暂时将将(1,0)记为。首首先先0=1，若若F中中的的元元素素就就是是Fp中中的的元元素素，则其其最最小小多多项式将式将总是是x，
36、因而，因而0=1的最小多的最小多项式式为x1。接下来，考接下来，考虑自身。由于自身。由于不是不是F3中的元素，因而中的元素，因而x也不是也不是F3中的元素。中的元素。然然而而，二二维向向量量空空间F中中的的3个个向向量量1=(0,1)，=(1,0)，2=(0,2)必定是必定是线性相关的。性相关的。进而可以得到一个以而可以得到一个以为根的二次方程，由于根的二次方程，由于220=221=0，因而因而的最小多的最小多项式式为x22，即定，即定义域的多域的多项式。式。三、最小多三、最小多项式与本原多式与本原多项式式接下来接下来计算算2的最小多的最小多项式，由于式，由于=2=(0,2)，因而，因而其最小
37、多其最小多项式式为x2。接接下下来来计算算=3的的最最小小多多项式式，首首先先计算算得得到到它它的的三三个个幂次如下次如下0=1=(0,1)，=3=(2,0)，2=6=(0,2)，由于由于2=20，因而，因而的最小多的最小多项式式为x22或者或者为x2+1。接接下下来来计算算本本原原元元=(1,2)=x+2的的最最小小多多项式式。首首先先计算算得得到它的三个到它的三个幂次如下次如下0=1=(0,1)，=(1,2)，2=(x+2)2x(mod x22)=(1,0)，由于由于2=+0，因而，因而的最小多的最小多项式式为x2x1或者或者为x2+2x+2。三、最小多三、最小多项式与本原多式与本原多项式
38、式以下以下设F是有限域，是有限域，K是是F的有的有q个元素的子域。个元素的子域。由由前前面面的的讨论知知可可以以将将F看看做做是是K上上的的一一个个向向量量空空间，故故F中的元素的个数是中的元素的个数是K中的元素个数中的元素个数q的的幂次。次。同同时q应是某个素数是某个素数p的的幂次，即次，即q=pm。因而存在某整数因而存在某整数n，使得，使得|F|=qn=pnm。F，将定理，将定理6.2.5中的素域中的素域Fp替替换为K，则可以得到可以得到的相的相对于域于域K的最小多的最小多项式式p(x)。为了得到了得到p(x)的具体表达式，需要引入如下几个引理的具体表达式，需要引入如下几个引理三、最小多三
39、、最小多项式与本原多式与本原多项式式引引理理6.2.3 F，则 K当当且且仅当当q=。特特别地地，x K，有方程，有方程xqx=0。证明明：K，若若=0，则q=；否否则设ord()=t，则t|(q1)，因而，因而q1=1，故，故q=，即即K中的中的q个元素个元素为方程方程xqx=0提供了提供了q个不同个不同的解。的解。同同时该方程也就只有方程也就只有这q个解，而无其它解。个解，而无其它解。三、最小多三、最小多项式与本原多式与本原多项式式引理引理6.2.4 若若p为素数，素数，则对于于1kp1，有，有p整除二整除二项式系数式系数 。证明明：由二：由二项式系数的定式系数的定义有有该分数的分子被分数
40、的分子被p整除，但分母不被整除，但分母不被p整除。整除。三、最小多三、最小多项式与本原多式与本原多项式式引理引理6.2.6设1,2,t是任意是任意p特征域中的元素，特征域中的元素，则k=1,2,3,证明明：首先当：首先当t=1时，结论成立。成立。当当t=2时，利用数学，利用数学归纳法法证明明 k=1,2,3,。若。若k=1，上述等式中的每个二上述等式中的每个二项式系数都是式系数都是p的倍数，的倍数，进而在而在p特特征域中征域中这些系数都是些系数都是0。因而。因而 。三、最小多三、最小多项式与本原多式与本原多项式式若若k=2，则因而当因而当k=2时结论成立。成立。以此以此为基基础，由数学，由数学
41、归纳法知法知t=2时，等式，等式 k=1,2,3,，成立。，成立。进而，由数学而，由数学归纳法知法知结论成立。成立。三、最小多三、最小多项式与本原多式与本原多项式式一般有限域中的最小多一般有限域中的最小多项式。式。首首先先若若Kx中中的的多多项式式p(x)=p0+p0 x+p2x2+pdxd以以为根根，即即p()=p0+p0+p22+pdd=0，且，且pi F，i=0,1,d则(p0+p1+p22+pdd)q=0，即，即p0q+p1qq+p2q2q+pdqdq=0，于是，于是p0+p1q+p2(q)2+pd(q)d=0=p(q)。因因而而若若是是p(x)的的根根，则q也也是是p(x)的的根根。
42、利利用用同同样的的推推导过程，我程，我们会会发现,等等也都是等等也都是p(x)的根。的根。三、最小多三、最小多项式与本原多式与本原多项式式定定义6.2.2 称称，q，,为相相对于于子子域域K的的共共轭根根系系，并并称称此此共共轭根根系系中中的的元元素素个个数数为的的次次数数，记为deg()。定定理理6.2.6 设F是是有有qn个个元元素素的的有有限限域域，则 F，若若相相对于于子子域域K的的共共轭根根系系中中的的元元素素个个数数为d，则d|n且且d是是满足足同同余余式式qd1(modt)的的最最小小正正整整数数，其其中中t=ord()。同。同时 t，若，若t=d+r，且，且0rd1，则三、最小
43、多三、最小多项式与本原多式与本原多项式式证明明：假假设0，则由由于于相相对于于子子域域K的的的的各各共共轭根根都都是是有有限限域域F中中的的元元素素，因因而而序序列列,q,中中必必定定会会出出现重复。重复。设 为序序列列,q,中中最最先先出出现重重复复的的元元素素，且且 ，其中，其中jd，则 因而因而ord()|qj(qd-j1)。但但ord()|(qn1)，即即gcd(ord(),qj)=1。因而。因而ord()|(qd-j1)，即即 ，也也即即 也也是是出出现了了重重复复的的元元素素，但但是是最最先先出出现重复的元素。因而重复的元素。因而j=0，即，即三、最小多三、最小多项式与本原多式与本
44、原多项式式但但F中有中有qn个元素，因而个元素，因而因因而而 。由由于于 是是最最先先出出现重重复复的的元元素素，因因而而必必定有定有gcd(d,n)=d，即，即d是是n的一个因子。的一个因子。因而因而的不同共的不同共轭根的个数是根的个数是n的一个因子。的一个因子。同同时，通通过前前面面的的讨论，发现d是是满足足式式qd1(mod t)的的最小正整数，其中最小正整数，其中t=ord()。综合以上合以上讨论知知结论成立。成立。三、最小多三、最小多项式与本原多式与本原多项式式由由定定理理6.2.6相相对于于子子域域K的的共共轭根根系系中中的的d个个元元素素,q,必必定定都都是是的的最最小小多多项式
45、式的的根根。因因而而若若定定义多多项式式f(x)=(x)(xq)(x)(x)，则多多项式式f(x)必定是必定是的最小多的最小多项式的一个因式。式的一个因式。并且并且定定理理6.2.7设有有限限域域F有有qn个个元元素素，K是是F的的一一个个有有q个个元元素素的子域。的子域。则 F，相相对于子域于子域K的最小多的最小多项式式为f(x)=(x)(xq)(x)(x)其其中中d=deg()，即即相相对于于子子域域K的的共共轭根根系系中中的的元元素素个个数。数。三、最小多三、最小多项式与本原多式与本原多项式式证明明：首先：首先相相对于子域于子域K的最小多的最小多项式式f(x)=(x)(xq)(x)(x)
46、=adxd+ad1xd1+a1x+a0，进而而f(x)q=(x)q(xq)q(x)q(x)q=adqxdq+ad1qxq(d1)+a1qxq+a0q又又(x)q=xq+(1)qq=xqq，因而，因而f(x)q=(xqq)(xq)(xq)(xq)=f(xq)三、最小多三、最小多项式与本原多式与本原多项式式但由但由f(x)的展开式的展开式应有有f(xq)=adxdq+ad1x q(d1)+a1xq+a0因因而而aiq=ai，i=0,1,d1，即即ai，i=0,1,d1，为域域K中中的的元素。元素。我我们已已经找找到到了了一一个个多多项式式f(x)，它它是是的的最最小小多多项式式的一个因式，且其系数
47、都在子域的一个因式，且其系数都在子域K中。中。进而我而我们可以得到可以得到结论：f(x)就是就是的相的相对于子域于子域K的最小多的最小多项式。式。三、最小多三、最小多项式与本原多式与本原多项式式例例6.2.10当当q=2，n=4时，x4+x+1是是F2x中中的的不不可可约多多项式式。利利用用此此多多项式式可可以以构构造造一一个个具具有有16个个元元素素的的域域F16。若若记=x mod x4+x+1，即即向向量量(0,0,1,0)所所对应的域元素，的域元素，则通通过计算可以得到如下运算表算可以得到如下运算表iideg(i)deg()最小多项式最小多项式0000111x+110010154(x)
48、(x2)(x4)(x8)=x4+x+120100154x4+x+13100054(x3)(x6)(x12)(x9)=x4+x3+x2+x+140011154x4+x+1iideg(i)deg()最小多项式最小多项式5011032(x5)(x10)=x2+x+16110054x4+x3+x2+x+171011154(x7)(x14)(x13)(x11)=x4+x3+180101154x4+x+19101054x4+x3+x2+x+110011132x2+x+1111110154x4+x3+112111154x4+x3+x2+x+1131101154x4+x3+1141001154x4+x3+11
49、5000111x+1三、最小多三、最小多项式与本原多式与本原多项式式在在这个表的个表的计算算过程中，程中，i=0：1在在任任意意域域中中的的最最小小多多项式式均均为x1；当当然然在在特特征征为2的域中的域中x1与与x+1是等同的。是等同的。i=1：由由例例6.2.9我我们发现的的最最小小多多项式式与与定定义这个个域域的的多多项式式相相同同。在在这个个例例子子中中，我我们利利用用了了x4+x+1来来定定义域域，因因而而必必然然满足足等等式式4=+1。有有疑疑问的的读者可以将者可以将(x)(x2)(x4)(x8)展开以便展开以便证明。明。i=2：由由于于,2,4,8互互为共共轭根根，因因而而他他们
50、具具有有相相同同的的最最小小多多项式式。进而而由由的的最最小小多多项式式为x4+x+1，可知可知2的最小多的最小多项式也是式也是x4+x+1。三、最小多三、最小多项式与本原多式与本原多项式式i=3：可可以以将将式式(x3)(x6)(x12)(x9)完完全全展展开开以以便便证明明3的的最最小小多多项式式为x4+x3+x2+x+1。我我们也也可可以以按按照照例例6.2.9的的方方法法来来给出出3的的最最小小多多项式式，即即由由于于3可可以以表表示示为一一个个四四维向向量量，因因而而3的的最最初初5个个幂次次中中必必然然存存在在一一个个线性性关关系系式式。下下面面再再介介绍一一个个上上述述方方法法的