数论与有限域第六章.ppt

《数论与有限域第六章.ppt》由会员分享，可在线阅读，更多相关《数论与有限域第六章.ppt（67页珍藏版）》请在三一办公上搜索。

1、第六章 有限域的抽象性质,第一节 有限域的加法结构,一、域的特征 二、有限域F中的元素个数,一、域的特征,设e为有限域F中的乘法单位元。定义F中的序列u0,u1,u2,如下u0=0,un=un-1+e,其中n=1,2,.则易知nZ，有un=ne，于是在此序列中，m和n，有um+n=(m+n)e=me+ne=um+un且umn=(mn)e=(mn)e2=mene=umun。由于F是有限域，因而序列u0,u1,u2,中的元素不可能都不相同，故可设存在整数c，使得u0=0,u1,u2,uk+c-1互不相同且uk+c=uk。又uk+c-uk=uc，即uc=ce=0。因而我们找到了一个整数c，使得ce=

2、0。一般地,一、域的特征,定义记有限域F的乘法单位元为e，如果存在正整数n，使得ne=0，则称满足此条件的最小正整数n为域F的特征。如果这样的正整数不存在，则称域F的特征为零。例 容易验证由前一章的例得到的域GF(8)的特征为2，由例得到域GF(9)的特征为3，而实数域与有理数域的特征则为0。,一、域的特征,定理若F是有限域，则F的特征c必定为素数。证明：假设相反，设正整数c=ab，其中1ac，1bc，则由上述有限域F中的序列u0,u1,u2,所具有的性质知uc=uaub。但uc=0，而ua与ub均不为0，如此与域中无零因子的性质相矛盾，因而c必定为素数。在以下的叙述中，记有限域的特征为字母p

3、，则易知序列u0,u1,u2,中第一个出现重复的元素是up=0，进而u0,u1,u2,up-1互不相同。,二、有限域F中的元素个数,定理有限域F中的元素个数q必定是某个素数p的幂次，即q=pm。证明：首先，容易验证域F的子集u0,u1,u2,up-1构成了F的一个子域，记为Fp。若F=Fp，则q=p，结论得证。否则设1F-Fp，则a,bFp，在F中都可以对应地找到一个元素a1+b，显然在F中共有p2个元素具有这样的形式，因而若域F中元素的数目q=p2，则定理得证。,二、有限域F中的元素个数,否则在F中选择不具有形式a1+b的元素2，则a,b,cFp，在F中都可以对应地找到一个元素a2+b1+c

4、，显然在F中共有p3个元素具有此形式，因而若域F中元素的数目q=p3，则定理得证。否则，我们在F中选择不具有形式a2+b1+c的元素3，。最终，在F中可以选定一组元素1,2,m-1，使得F中的每个元素都有唯一的表达式：=a1+a21+a32+am-1m-1，其中aiFp，i=1,2,m-1。由于每个ai有p个可能的取值，因而F中恰有pm个元素。定理得证,二、有限域F中的元素个数,通过定理，对有限域F的加法结构我们可以得到如下认识：有限域F中的元素可以看做是域Fp中元素构成的m元组，且(a1,a2,am)+(b1,b2,bm)=(a1b1,a2+b2,am+bm)接下来，我们来研究域F的乘法结构

5、。,第二节 有限域的乘法结构,一、元素的阶二、本原元 三、最小多项式与本原多项式,一、元素的阶,以下设F为有限域，F*为有限域F中的所有非零元素构成的集合，F*，考察由的各个幂次所构成的序列e,2,n,的性质。首先由域F对乘法运算的封闭性，知i，iF，又F是有限域，因而序列e,2,n,中必然会出现重复。设e,2,k+t-1互不相同且k=k+t，则k=0；否则若k0，则由k=k+t得到k-1=k+t-1，这与e,2,k+t-1互不相同相矛盾，进而t=e。一般地,一、元素的阶,定义 记有限域F的乘法单位元为e，则称使得等式t=e成立的最小正整数t，t1，为的阶，记为ord()。通常，取不同值，的阶

6、相应地也会有不同的取值，并且计算有可能也会很困难。但是，在域F中利用以下结论可以很明确地确定出t，t1，阶元素的个数。,一、元素的阶,定理设有限域F具有q个元素，F*，若的阶为t，则t|(q-1)。证明：由域的定义，F*构成了乘法群，由于的阶为t，即t=e，因而e,2,t-1构成了F*的子群。拉格朗日定理子群中的元素个数一定会是整个群的元素个数的因子，因而t|(q-1)。,一、元素的阶,引理设F为有限域，若p(x)是Fx中的m次多项式，则在域F中方程p(x)=0至多有m个不同的根。证明：对m进行数学归纳。若m=1，此时p(x)为一次多项式，即方程p(x)=0具有形式ax+b=0，显然该方程只有

7、一个根x=-a-1b。若m2，且方程p(x)=0没有根，则定理得证；否则，设为方程p(x)=0的根，即 p()=0，以(x-)除以p(x)由带余数除法可以得到p(x)=q(x)(x-)+r(x)，其中deg(r(x)deg(x-)，或者r(x)=0，,一、元素的阶,从而r(x)是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)的次数为m-1，由归纳假设方程q(x)=0至多有m-

8、1个根，因而方程p(x)=0至多有m个根。,一、元素的阶,例设Z8为整数模8的剩余类环，即定义了模8的加法和乘法运算的集合0,1,2,7。在这个环中，通过验证我们会发现多项式方程x2-1=0有4个不同的根x=1,3,5,7。即我们竟然得到了一个有4个根的二次方程，这似乎与我们给出的引理矛盾。但是需要注意的是Z8中有零因子2和4，因而不是域，故并不矛盾。,一、元素的阶,推论 若ord()=t，则每个满足方程xt=e的域F中的元素都必定是的幂。证明：若ord()=t，即t=e，则(i)t-e=(t)i-e=0，即t个元素e,2,t-1是方程xt-e=0的t个不同的根，而由引理该方程不会再有其它的根

9、！即每个满足方程xt=e的域F中的元素都必定是的幂。但是正如下面的引理所述的，并不是的每个幂次都有阶t。,一、元素的阶,引理若ord()=t，则ord(i)=t/gcd(i,t)。证明：首先，易知0，有s=e当且仅当ord()|s。其次，设d=gcd(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(

10、i)|(t/d)，就得到ord(i)=t/d，也即ord(i)=t/gcd(i,t)。,一、元素的阶,例设域F中的元素的阶ord()=8，则利用引理可以计算i，i=0,1,7的阶的结果如下表：表6-1 域F中各元素阶列表,表6-1 中有：4个8阶的元素，2个4阶的元素，1个2阶的元素，以及1个1阶的元素；,一、元素的阶,定理设t为整数，则在域F中或者没有t阶元素，或者恰有(t)个t阶元素。证明：若在域F中没有t阶元素，则定理得证。反之，若ord()=t，正如上面所观察到的每个t阶元素都在集合1,2,t-1中。但是由引理，i的阶为t当且仅当gcd(t,i)=1。因而这样的i恰有(t)个。,一、元

11、素的阶,到此，对于有q个元素的有限域F的元素的阶我们有这样的认识：给定正整数t，若t(q-1)，则在域F中不存在t阶元素；若t|(q-1)，则在域F中或者没有t阶元素，或者恰有(t)个t阶元素。接下来我们证明若t确实整除q-1，则在域F中将总是存在有(t)个t阶元素。在给出具体证明之前，再来看另外一个例子。,一、元素的阶,例设q=9，则q-1=8，进而t的可能取值为1，2，4，8。又对于t的每一个可能取值，t阶元素的个数或者为0或者为(t)个。由欧拉函数的性质，计算得到t和(t)的取值如下表：,注：(t)列的和为8，与域F中的非零元素的个数相同。,一、元素的阶,定理若n为正整数，则。证明：设S

12、n为有理数集：，而Tn为Sn中的既约分数构成的集合，即Tn中的元素的分母为n，分子与n相对互素，则|Sn|=n且|Tn|=(n)(例如 且)。,一、元素的阶,接下来若设集合Sn中的所有分数都已进行了约简，则集合Sn中的每一个分数的分母d是n的因子，其分子e是与n相对互素且介于区间1ed的整数。反之，若d是n的正因子，1ed，且(e,d)=1，则分数e/d必是集合Sn中某个分数的约简形式。进而，对于n的所有因子d，Sn将会分解为若干不相交的集合Td的并集，即，进而。同时由于|Sn|=n，|Td|=(d)。因而结论得证。,一、元素的阶,例计算(35)。解：按照欧拉函数的定义，可以在1，2，3，35

13、中逐个测试其是否与35相对互素。然而，由定理应有(1)+(5)+(7)+(35)=35，同时，(1)=1，(5)=4，(7)=6，因而(35)=351-4-6=24。,一、元素的阶,定理设F是有q个元素的有限域，t为正整数。若t(q-1)，则域F中不存在t阶元素；若t|(q-1)，则域F中恰有(t)个t阶元素。证明：只需证明：若t|(q-1)，则域F中恰有(t)个t阶元素。对于q-1的每个正因子t，记域F中t阶元素的个数为(t)。则由域F中的每个非零元素的阶都必定整除q-1，可以得到又，进而但是对于所有的t，(t)-(t)0。因而对于q-1的每个正因子t，都有(t)=(t)。,一、元素的阶,推

14、论6.2.2 在每个有限域中，都至少存在一个（事实上恰有(q-1)个）q-1阶元素。因而任意有限域的乘法群都是循环群。,二、本原元,定义称有限域F中阶为q-1的元素，即循环群F*=F-0的生成元，为本原元。例给出域F=Z5以及域F=Z7中的本原元。解：首先由上节的定理，域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，而3的阶为4/gcd(4,3)=4，4的阶为4/gcd(4,2)=2，因而2与3是域Z5中的本原元。,

15、二、本原元,例给出域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，因而3的阶为6，而5的阶为6/gcd(6,5)=6，6的阶为6/gcd(6,3)=2，因而3与5是域Z7中的本原元。,二、本原元,高斯算法：第一步：设i=1，取域F中的任意一个非零元1，且记ord(1)=t1。第二步：若ti=q-1，则算法停止：i即为所寻找的本原

16、元；否则转第三步。第三步：在域F中选一个非i的幂次的非零元，设ord()=s，若s=q-1，则令i+1=，算法停止；否则转第四步。第四步：寻找ti的一个因子d，s的一个因子e，使得gcd(d,e)=1且de=lcm(ti,s)。设，ti+1=lcm(ti,s)。i值加1，返回第二步。,二、本原元,注意，在这个算法中：由于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是可能的。例如，m=12，n=18时，可以

17、取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)的一个倍数，因而这个算法最终必定会终止于一个本原元。,二、本原元,例利用多项式f(x)=x3+2x+1构造一个有限域，并找出域中的本原元。解：这里只给出了构造域的多项式，并未给出构造域所需的欧氏环，因而可以任意选一个欧氏环，只要保证f(x)为此域中的不可约多项式即可。注意到在F3中f(0)=1，f(1)=f(2)=2，因而该多项式是F3x中的一个不可约多项式，以此可以构

18、造一个具有27个元素的有限域F。域F中的元素都可以看做是三维向量(a,b,c)，其中a,b,cF3=0,1,2。,二、本原元,在域F中注意到x3x+2(mod x3+2x+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，为了计

19、算1的阶，先来计算x的各个幂次对f(x)取模的结果x01(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+

20、2(mod x3+2x+1),x12x3+x2+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+2

21、x+1)x232x2+2x(mod x3+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=q-1=26，算法停止；1就是F中的本原元。,二、本原元,例利用多项式f(x)=x2-2构造一个有限域，并找出这个域中的本原元。解：这里只给出了构造域的多项式，并未给出构造域所需的欧氏环，因而需要选择一个欧氏环，并保证f(x)为此域中的不可约多项式。注意到在F3中f(0)=1，f(1)=f(2)=2，因而该多项式是F3x

22、中的一个不可约多项式，以此可以构造一个具有9个元素的有限域F。域F中的元素都可以看做是二维向量(a,b)，其中a,bF3=0,1,2。,二、本原元,在域F中注意到x22(mod x2-2)，因而可定义域F中的加法与乘法运算如下：(a1,b1)+(a2,b2)=(a1+a2,b1+b2)。(a1,b1)(a2,b2)=(a1b2+a2b1,b1b2+2a1a2)接下来利用高斯算法寻找这个域中的本原元。首先取1=(1,0)=x，为了计算1的阶，先来计算1=(1,0)=x的各个幂次对f(x)取模的结果x01(mod x2-2),x1x(mod x2-2),x22(mod x2-2)x32x(mod

23、x2-2)，x42x21(mod x2-2)，,二、本原元,因而1=(1,0)=x的阶为4，即在高斯算法中有t1=4。由于t1q-1=8，因而1不是本原元，接着转至第3步，需要选择一个不是1的幂次的元素，例如可以选=(1,2)=x+2，则2=(x+2)2x(modx2-2)=(1,0)，,以二维向量表示为表6-3 1=(1,0)=x各个幂次的向量表示,二、本原元,类似地可以得到=(1,2)=x+2的各个幂次对f(x)取模的结果的向量表示因而的阶s=8=q-1，则令2=，算法停止；2就是F中的本原元。,表6-4=(1,2)=x+2的各个幂次的向量表示,二、本原元,例6.2.8 在上例中，由于f(

24、x)=x2-2在F5中也没有2的平方根，因而该多项式也是F5x中的一个不可约多项式，由此也可以构造一个具有25个元素的有限域F如下。首先域F中的元素都可以看做是二维向量(a,b)，其中a,bF5=0,1,2,3,4。在域F中注意到x22(mod x2-2)，因而可定义域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，即在

25、高斯算法中t1=8。由于t1q-1=24，因而1不是本原元，接着转至第3步，需要选择一个不是1的幂次的元素，例如可以选=(1,1)=x+1，则 2=(x+1)2 2x+3(modx2-2)=(2,3)，类似地可以得到的各个幂次对f(x)取模的结果的向量表示如下,表6-5 1=(1,0)=x的各个幂次的向量表示,二、本原元,因而的阶为12，进而1=(1,0)，=(1,1)，t1=8，s=12，转到第四步。由于lcm(8,12)=24，满足条件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)=21

26、2+21=2x2+2x2x+4(mod x2-2)且2的阶为lcm(8,12)=24。因而t2=24，返回第二步，算法停止；2x+4即为F中的本原元。,三、最小多项式与本原多项式,设F是有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()为所有这样的多项式构成的集合，即S(

27、)=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)的倍式。称集合S()中次数最低的这个多项式p(x)为域F中以为根的最小多项式。若要求p(x)是首一多项式，则这样的p(x)是唯一的，并且是不可约多项式。这是由于，若p(x)=a(x)b(x)，则由于

28、p()=0，必然会得到a()=0或b()=0，这与deg(p)的最小性相矛盾。,三、最小多项式与本原多项式,定理6.2.5 设F是有pm个元素的有限域，则F，若Fpx中存在唯一的首一多项式p(x)，使得p()=0，deg(p)m，若f(x)为Fp(x)中另外一个以为根的多项式，则p(x)|f(x)。则称p(x)为的相对于F的子域Fp的最小多项式，若为本原元，则称其所对应的最小多项式为本原多项式。,三、最小多项式与本原多项式,例计算例所给域中某些个元素的最小多项式。解：考虑元素(1,0)的幂次，这里暂时将(1,0)记为。首先0=1，若F中的元素就是Fp中的元素，则其最小多项式将总是x-，因而0=

29、1的最小多项式为x-1。接下来，考虑自身。由于不是F3中的元素，因而x-也不是F3中的元素。然而，二维向量空间F中的3个向量1=(0,1)，=(1,0)，2=(0,2)必定是线性相关的。进而可以得到一个以为根的二次方程，由于2-20=2-21=0，因而的最小多项式为x2-2，即定义域的多项式。,三、最小多项式与本原多项式,接下来计算2的最小多项式，由于=2=(0,2)，因而其最小多项式为x-2。接下来计算=3的最小多项式，首先计算得到它的三个幂次如下0=1=(0,1)，=3=(2,0)，2=6=(0,2)，由于2=20，因而的最小多项式为x2-2或者为x2+1。接下来计算本原元=(1,2)=x

30、+2的最小多项式。首先计算得到它的三个幂次如下0=1=(0,1)，=(1,2)，2=(x+2)2x(mod x2-2)=(1,0)，由于2=+0，因而的最小多项式为x2-x-1或者为x2+2x+2。,三、最小多项式与本原多项式,以下设F是有限域，K是F的有q个元素的子域。由前面的讨论知可以将F看做是K上的一个向量空间，故F中的元素的个数是K中的元素个数q的幂次。同时q应是某个素数p的幂次，即q=pm。因而存在某整数n，使得|F|=qn=pnm。F，将定理中的素域Fp替换为K，则可以得到的相对于域K的最小多项式p(x)。为了得到p(x)的具体表达式，需要引入如下几个引理,三、最小多项式与本原多项

31、式,引理 F，则K当且仅当q=。特别地，xK，有方程xq-x=0。证明：K，若=0，则q=；否则设ord()=t，则t|(q-1)，因而q-1=1，故q=，即K中的q个元素为方程xq-x=0提供了q个不同的解。同时该方程也就只有这q个解，而无其它解。,三、最小多项式与本原多项式,引理 若p为素数，则对于1kp-1，有p整除二项式系数。证明：由二项式系数的定义有该分数的分子被p整除，但分母不被p整除。,三、最小多项式与本原多项式,引理设1,2,t是任意p特征域中的元素，则k=1,2,3,证明：首先当t=1时，结论成立。当t=2时，利用数学归纳法证明 k=1,2,3,。若k=1，上述等式中的每个二

32、项式系数都是p的倍数，进而在p特征域中这些系数都是0。因而。,三、最小多项式与本原多项式,若k=2，则因而当k=2时结论成立。以此为基础，由数学归纳法知t=2时，等式 k=1,2,3,，成立。进而，由数学归纳法知结论成立。,三、最小多项式与本原多项式,一般有限域中的最小多项式。首先若Kx中的多项式p(x)=p0+p0 x+p2x2+pdxd以为根，即p()=p0+p0+p22+pdd=0，且piF，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

33、)的根。利用同样的推导过程，我们会发现,等等也都是p(x)的根。,三、最小多项式与本原多项式,定义6.2.2 称，q，,为相对于子域K的共轭根系，并称此共轭根系中的元素个数为的次数，记为deg()。定理 设F是有qn个元素的有限域，则F，若相对于子域K的共轭根系中的元素个数为d，则d|n且d是满足同余式qd1(modt)的最小正整数，其中t=ord()。同时 t，若t=d+r，且0rd-1，则,三、最小多项式与本原多项式,证明：假设0，则由于相对于子域K的的各共轭根都是有限域F中的元素，因而序列,q,中必定会出现重复。设 为序列,q,中最先出现重复的元素，且，其中jd，则 因而ord()|qj

34、(qd-j-1)。但ord()|(qn-1)，即gcd(ord(),qj)=1。因而ord()|(qd-j-1)，即，也即 也是出现了重复的元素，但是最先出现重复的元素。因而j=0，即,三、最小多项式与本原多项式,但F中有qn个元素，因而因而。由于 是最先出现重复的元素，因而必定有gcd(d,n)=d，即d是n的一个因子。因而的不同共轭根的个数是n的一个因子。同时，通过前面的讨论，发现d是满足式qd1(mod t)的最小正整数，其中t=ord()。综合以上讨论知结论成立。,三、最小多项式与本原多项式,由定理6.2.6相对于子域K的共轭根系中的d个元素,q,必定都是的最小多项式的根。因而若定义多

35、项式f(x)=(x-)(x-q)(x-)(x-)，则多项式f(x)必定是的最小多项式的一个因式。并且定理设有限域F有qn个元素，K是F的一个有q个元素的子域。则F，相对于子域K的最小多项式为f(x)=(x-)(x-q)(x-)(x-)其中d=deg()，即相对于子域K的共轭根系中的元素个数。,三、最小多项式与本原多项式,证明：首先相对于子域K的最小多项式f(x)=(x-)(x-q)(x-)(x-)=adxd+ad-1xd-1+a1x+a0，进而f(x)q=(x-)q(x-q)q(x-)q(x-)q=adqxdq+ad-1qxq(d-1)+a1qxq+a0q又(x-)q=xq+(-1)qq=xq

36、-q，因而f(x)q=(xq-q)(xq-)(xq-)(xq-)=f(xq),三、最小多项式与本原多项式,但由f(x)的展开式应有f(xq)=adxdq+ad-1x q(d-1)+a1xq+a0因而aiq=ai，i=0,1,d-1，即ai，i=0,1,d-1，为域K中的元素。我们已经找到了一个多项式f(x)，它是的最小多项式的一个因式，且其系数都在子域K中。进而我们可以得到结论：f(x)就是的相对于子域K的最小多项式。,三、最小多项式与本原多项式,例6.2.10当q=2，n=4时，x4+x+1是F2x中的不可约多项式。利用此多项式可以构造一个具有16个元素的域F16。若记=x mod x4+x

37、+1，即向量(0,0,1,0)所对应的域元素，则通过计算可以得到如下运算表,三、最小多项式与本原多项式,在这个表的计算过程中，i=0：1在任意域中的最小多项式均为x-1；当然在特征为2的域中x-1与x+1是等同的。i=1：由例6.2.9我们发现的最小多项式与定义这个域的多项式相同。在这个例子中，我们利用了x4+x+1来定义域，因而必然满足等式4=+1。有疑问的读者可以将(x-)(x-2)(x-4)(x-8)展开以便证明。i=2：由于,2,4,8互为共轭根，因而他们具有相同的最小多项式。进而由的最小多项式为x4+x+1，可知2的最小多项式也是x4+x+1。,三、最小多项式与本原多项式,i=3：可

38、以将式(x-3)(x-6)(x-12)(x-9)完全展开以便证明3的最小多项式为x4+x3+x2+x+1。我们也可以按照例6.2.9的方法来给出3的最小多项式，即由于3可以表示为一个四维向量，因而3的最初5个幂次中必然存在一个线性关系式。下面再介绍一个上述方法的变形。这里我们暂时记3=，则通过计算可以得到3=的最初5个幂次依次为 1=0001=3=10002=6=11003=9=10104=12=1111,三、最小多项式与本原多项式,下面我们通过基本的列变换找出这5个四维向量的一个线性相关关系式。首先将第二列加到第一列，得到00011000010010100111 接着将第三列加到第一列，得到

39、00011000010000101111,三、最小多项式与本原多项式,i=4：由于,2,4,8互为共轭根，因而他们具有相同的最小多项式。进而由的最小多项式为x4+x+1，可知4的最小多项式也是x4+x+1。i=5：由于5的最小多项式为(x-5)(x-10)，将其完全展开得到(x-5)(x-10)=x2-5x-10 x+15=x2-(2+)x-(2+1)x+1=x2+x+1。i=6：由于3,6,12,9互为共轭根，因而他们具有相同的最小多项式。进而由3的最小多项式为x4+x3+x2+x+1，可知6的最小多项式也是x4+x3+x2+x+1。,三、最小多项式与本原多项式,i=7：这里我们暂时记7=，

40、则通过计算可以得到7=的最初5个幂次依次为 1=0001=7=10112=14=1001 3=21=6=1100（注意5=15=1）4=28=13=1101下面我们通过基本的列变换找出这5个四维向量的一个线性相关关系式。首先将第四列加到第一列，得到10010011000111000101,三、最小多项式与本原多项式,接着将第三列加到第四列，得到10010010000111000101此时这个矩阵中有第一行与第三、四行之和为0，即1+3+4=0。因而=7的最小多项式为x4+x3+1。当然我们也可以将式(x-7)(x-14)(x-13)(x-11)完全展开以便证明7的最小多项式为x4+x3+1。,