数论与有限域 .pptx

《数论与有限域 .pptx》由会员分享，可在线阅读，更多相关《数论与有限域 .pptx（67页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第一节第一节 有限域的加法结构有限域的加法结构 一、域的特征一、域的特征 二、二、有限域有限域F F中的元素个数中的元素个数 第1页/共67页一、域的特征一、域的特征设设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。一般地一般地 第2页/共67页一、域的特征一、域的特征定定义义记记有有限限域域F的的乘乘法法单单位位元元为为e，如如果果存存在在正正整整数数n，使使得得ne=0，则则称称满满足足此此条条件件的的最最小小正正整整数数n为为域域F的的特特征征。如如果果这这样样的的正正整整数数不不存存在在，则则称称域域F的的特征为零。特征为零。例例 容易验证由前一章的例得到的域容

3、易验证由前一章的例得到的域GF(8)的特征为的特征为2，由例得到域由例得到域GF(9)的特征为的特征为3，而实数域与有理数域的特征则为而实数域与有理数域的特征则为0。第3页/共67页一、域的特征一、域的特征定理定理若若F是有限域，则是有限域，则F的特征的特征c必定为素数。必定为素数。证证明明：假假设设相相反反，设设正正整整数数c=ab，其其中中1ac，1bc，则则由由上上述述有有限限域域F中中的的序序列列u0,u1,u2,所具有的性质知所具有的性质知uc=uaub。但但uc=0，而而ua与与ub均均不不为为0，如如此此与与域域中中无无零零因因子子的的性质相矛盾，因而性质相矛盾，因而c必定为素数

4、。必定为素数。在在以以下下的的叙叙述述中中，记记有有限限域域的的特特征征为为字字母母p，则则易易知知序列序列u0,u1,u2,中第一个出现重复的元素中第一个出现重复的元素是是up=0，进而进而u0,u1,u2,up1互不相同。互不相同。第4页/共67页二、二、有限域有限域F F中的元素个数中的元素个数定定理理有有限限域域F中中的的元元素素个个数数q必必定定是是某某个个素素数数p的的幂幂次次，即即q=pm。证证明明：首首先先，容容易易验验证证域域F的的子子集集u0,u1,u2,up1构成了构成了F的一个子域，记为的一个子域，记为Fp。若若F=Fp，则，则q=p，结论得证。，结论得证。否否则则设设

5、1 FFp，则则 a,b Fp，在在F中中都都可可以以对对应应地地找找到到一一个个元元素素a1+b，显显然然在在F中中共共有有p2个个元元素素具具有有这这样样的的形形式式，因因而而若若域域F中中元元素素的的数数目目q=p2，则定理得证。则定理得证。第5页/共67页二、二、有限域有限域F F中的元素个数中的元素个数否否则则在在F中中选选择择不不具具有有形形式式a1+b的的元元素素2，则则 a,b,c Fp，在在 F中中 都都 可可 以以 对对 应应 地地 找找 到到 一一 个个 元元 素素a2+b1+c，显显然然在在F中中共共有有p3个个元元素素具具有有此此形形式式，因而若域因而若域F中元素的数

6、目中元素的数目q=p3，则定理得证。，则定理得证。否否则则，我我们们在在F中中选选择择不不具具有有形形式式a2+b1+c的的元元素素3，。最最终终，在在F中中可可以以选选定定一一组组元元素素1,2,m1，使使得得 F中中 的的 每每 个个 元元 素素 都都 有有 唯唯 一一 的的 表表 达达 式式：=a1+a21+a32+am1m1，其其 中中 ai Fp，i=1,2,m1。由由于于每每个个ai有有p个个可可能能的的取取值值，因因而而F中恰有中恰有pm个元素。定理得证个元素。定理得证 第6页/共67页二、二、有限域有限域F F中的元素个数中的元素个数通通过过定定理理，对对有有限限域域F的的加加

7、法法结结构构我我们们可可以以得得到到如如下下认识：认识：有有限限域域F中中的的元元素素可可以以看看做做是是域域Fp中中元元素素构构成成的的m元元组，且组，且(a1,a2,am)+(b1,b2,bm)=(a1b1,a2+b2,am+bm)接下来，我们来研究域接下来，我们来研究域F的乘法结构。的乘法结构。第7页/共67页第二节第二节 有限域的乘法结构有限域的乘法结构 一、元素的阶一、元素的阶二、本原元二、本原元 三、最小多项式与本原多项式三、最小多项式与本原多项式第8页/共67页一、元素的阶一、元素的阶以以下下设设F为为有有限限域域，F*为为有有限限域域F中中的的所所有有非非零零元元素素构构成成的

8、的集集合合，F*，考考察察由由的的各各个个幂幂次次所所构构成成的的序列序列e,2,n,的性质。的性质。首首先先由由域域F对对乘乘法法运运算算的的封封闭闭性性，知知 i，i F，又又F是是有有限限域域，因因而而序序列列e,2,n,中中必必然然会会出现重复。出现重复。设设e,2,k+t1互不相同且互不相同且k=k+t，则，则k=0；否则若否则若k0，则由，则由k=k+t得到得到k1=k+t1，这与这与e,2,k+t1互不相同相矛盾，进而互不相同相矛盾，进而t=e。一般地一般地第9页/共67页一、元素的阶一、元素的阶定定义义 记记有有限限域域F的的乘乘法法单单位位元元为为e，则则称称使使得得等等式式

9、t=e成立成立的最小正整数的最小正整数t，t1，为，为的阶，记为的阶，记为ord()。通通常常，取取不不同同值值，的的阶阶相相应应地地也也会会有有不不同同的的取取值值，并并且且计计算算有有可可能能也也会会很很困困难难。但但是是，在在域域F中中利利用用以以下下结结论论可可以以很很明明确确地地确确定定出出t，t1，阶阶元元素素的的个数。个数。第10页/共67页一、元素的阶一、元素的阶定定理理设设有有限限域域F具具有有q个个元元素素，F*，若若的的阶阶为为t，则则t|(q1)。证证明明：由由域域的的定定义义，F*构构成成了了乘乘法法群群，由由于于的的阶阶为为t，即，即t=e，因因而而e,2,t1构构

10、成成了了F*的的子子群群。拉拉格格朗朗日日定定理理子子群群中中的的元元素素个个数数一一定定会会是是整整个个群群的的元元素素个个数数的的因子，因而因子，因而t|(q1)。第11页/共67页一、元素的阶一、元素的阶引引理理设设F为为有有限限域域，若若p(x)是是Fx中中的的m次次多多项项式式，则则在域在域F中方程中方程p(x)=0至多有至多有m个不同的根。个不同的根。证明证明：对：对m进行数学归纳。进行数学归纳。若若m=1，此此时时p(x)为为一一次次多多项项式式，即即方方程程p(x)=0具具有有形式形式ax+b=0，显然该方程只有一个根，显然该方程只有一个根x=a1b。若若m2，且方程，且方程p

11、(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，第12页/共67页一、元素的阶一、元素的阶从从而而r(x)是是Fx中中的的常常数数多多项项式式，也也即即域域F中中的的一一个个元元素。由于素。由于p()=0，因而，因而p()=q()()+r()=0，即，即r()=0，而而r(x)是域是域F中的一个元素，因而中的一个元素，因而r(x)=0，于是，于是p(x)=q(x

12、)(x)，并并且且方方程程p(x)=0的的任任意意一一个个不不等等于于的的根根都都是是方方程程q(x)=0的根。的根。但但是是q(x)的的次次数数为为m1，由由归归纳纳假假设设方方程程q(x)=0至至多多有有m1个根，因而方程个根，因而方程p(x)=0至多有至多有m个根。个根。第13页/共67页一、元素的阶一、元素的阶例例设设Z8为整数模为整数模8的剩余类环，即的剩余类环，即定义了模定义了模8的加法和乘法运算的集合的加法和乘法运算的集合0,1,2,7。在在这这个个环环中中，通通过过验验证证我我们们会会发发现现多多项项式式方方程程x21=0有有4个不同的根个不同的根x=1,3,5,7。即即我我们

13、们竟竟然然得得到到了了一一个个有有4个个根根的的二二次次方方程程，这这似似乎乎与与我我们们给给出出的的引引理理矛矛盾盾。但但是是需需要要注注意意的的是是Z8中中有有零因子零因子2和和4，因而不是域，故并不矛盾。，因而不是域，故并不矛盾。第14页/共67页一、元素的阶一、元素的阶推推论论 若若ord()=t，则则每每个个满满足足方方程程xt=e的的域域F中中的的元元素都必定是素都必定是的幂。的幂。证明证明：若：若ord()=t，即，即t=e，则，则(i)te=(t)ie=0，即即t个个元元素素e,2,t1是是方方程程xte=0的的t个个不不同同的的根根，而由引理该方程不会再有其它的根！即而由引理

14、该方程不会再有其它的根！即每个满足方程每个满足方程xt=e的域的域F中的元素都必定是中的元素都必定是的幂。的幂。但但是是正正如如下下面面的的引引理理所所述述的的，并并不不是是的的每每个个幂幂次次都都有阶有阶t。第15页/共67页一、元素的阶一、元素的阶引理引理若若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()=

15、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)。第16页/共67页一、元素的阶一、元素的阶例例设设域域F中中的的元元素素的的阶阶ord()=8，则则利利用用引引理理可可以以计计算算i，i=0,1,7的阶的结果如下表：的阶的结果如下表：表表61 域域F中各元素阶列表中各元素阶列表 igcd(i,8)

16、i081118224318442518624718表表61 中有：中有：4个个8阶的元素，阶的元素，2个个4阶的元素，阶的元素，1个个2阶的元素，阶的元素，以及以及1个个1阶的元素；阶的元素；第17页/共67页一、元素的阶一、元素的阶定定理理设设t为为整整数数，则则在在域域F中中或或者者没没有有t阶阶元元素素，或或者者恰恰有有(t)个个t阶元素。阶元素。证明证明：若在域：若在域F中没有中没有t阶元素，则定理得证。阶元素，则定理得证。反反之之，若若ord()=t，正正如如上上面面所所观观察察到到的的每每个个t阶阶元元素素都在集合都在集合1,2,t1中。中。但是由引理，但是由引理，i的阶为的阶为t

17、当且仅当当且仅当gcd(t,i)=1。因而这样的因而这样的i恰有恰有(t)个。个。第18页/共67页一、元素的阶一、元素的阶到到此此，对对于于有有q个个元元素素的的有有限限域域F的的元元素素的的阶阶我我们们有有这这样的认识：样的认识：1.给给定定正正整整数数t，若若t(q1)，则则在在域域F中中不不存存在在t阶阶元元素；素；2.若若t|(q1)，则则在在域域F中中或或者者没没有有t阶阶元元素素，或或者者恰恰有有(t)个个t阶元素。阶元素。接接下下来来我我们们证证明明若若t确确实实整整除除q1，则则在在域域F中中将将总总是是存存在在有有(t)个个t阶阶元元素素。在在给给出出具具体体证证明明之之前

18、前，再再来来看另外一个例子。看另外一个例子。第19页/共67页一、元素的阶一、元素的阶例例设设q=9，则，则q1=8，进而，进而t的可能取值为的可能取值为1，2，4，8。又对于又对于t的每一个可能取值，的每一个可能取值，t阶元素的个数或者阶元素的个数或者为为0或者为或者为(t)个。个。由欧拉函数的性质，计算得到由欧拉函数的性质，计算得到t和和(t)的取值如下表：的取值如下表：t(t)11214284注：注：(t)列的和为列的和为8，与域，与域F中的非零中的非零元素的个数相同。元素的个数相同。第20页/共67页一、元素的阶一、元素的阶定理定理若若n为正整数，则为正整数，则 。证明证明：设：设Sn

19、为有理数集：为有理数集：，而，而Tn为为Sn中的既约分数构成的集合，即中的既约分数构成的集合，即Tn中的元素的分母为中的元素的分母为n，分子与，分子与n相对互素，则相对互素，则|Sn|=n且且|Tn|=(n)(例如例如 且且 )。第21页/共67页一、元素的阶一、元素的阶接下来若设集合接下来若设集合Sn中的所有分数都已进行了约简，则中的所有分数都已进行了约简，则集合集合Sn中的每一个分数的分母中的每一个分数的分母d是是n的因子，的因子，其分子其分子e是与是与n相对互素且介于区间相对互素且介于区间1ed的整数。的整数。反之，若反之，若d是是n的正因子，的正因子，1ed，且，且(e,d)=1，则，

20、则分数分数e/d必是集合必是集合Sn中某个分数的约简形式。中某个分数的约简形式。进进而而，对对于于n的的所所有有因因子子d，Sn将将会会分分解解为为若若干干不不相相交交的集合的集合Td的并集，的并集，即即 ，进而，进而 。同时由于同时由于|Sn|=n，|Td|=(d)。因而结论得证。因而结论得证。第22页/共67页一、元素的阶一、元素的阶例例计算计算(35)。解解：按按照照欧欧拉拉函函数数的的定定义义，可可以以在在1，2，3，35中逐个测试其是否与中逐个测试其是否与35相对互素。相对互素。然而，由定理应有然而，由定理应有(1)+(5)+(7)+(35)=35，同时，同时，(1)=1，(5)=4

21、，(7)=6，因而因而(35)=35146=24。第23页/共67页一、元素的阶一、元素的阶定定理理设设F是是有有q个个元元素素的的有有限限域域，t为为正正整整数数。若若t(q1)，则则域域F中中不不存存在在t阶阶元元素素；若若t|(q1)，则则域域F中中恰恰有有(t)个个t阶阶元元素。素。证明证明：只需证明：若：只需证明：若t|(q1)，则域，则域F中恰有中恰有(t)个个t阶元素。阶元素。对对于于q1的的每每个个正正因因子子t，记记域域F中中t阶阶元元素素的的个个数数为为(t)。则则由由域域F中的每个非零元素的阶都必定整除中的每个非零元素的阶都必定整除q1，可以得到，可以得到又又 ，进而，进

22、而但但是是对对于于所所有有的的t，(t)(t)0。因因而而对对于于q1的的每每个个正正因因子子t，都有都有(t)=(t)。第24页/共67页一、元素的阶一、元素的阶推推论论在在每每个个有有限限域域中中，都都至至少少存存在在一一个个（事事实实上上恰恰有有(q1)个个）q1阶阶元元素素。因因而任意有限域的乘法群都是循环群。而任意有限域的乘法群都是循环群。第25页/共67页二、本原元二、本原元 定定义义称称有有限限域域F中中阶阶为为q1的的元元素素，即即循循环环群群F*=F0的生成元，为本原元。的生成元，为本原元。例例给出域给出域F=Z5以及域以及域F=Z7中的本原元。中的本原元。解解：首首先先由由

23、上上节节的的定定理理，域域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中的本原元。中的本原元。第26页/共67页二、本原元二、本原元 例例给出域给出域F=Z5以及域以及域F=Z7中的本原元。中的本原元

24、。解解：域域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中的本原元。中的本原元。第27页/共67页二、本原元二、本原元 高斯算

25、法：高斯算法：第第一一步步：设设i=1，取取域域F中中的的任任意意一一个个非非零零元元1，且且记记ord(1)=t1。第第二二步步：若若ti=q1，则则算算法法停停止止：i即即为为所所寻寻找找的的本本原原元；否则转第三步。元；否则转第三步。第第三三步步：在在域域F中中选选一一个个非非i的的幂幂次次的的非非零零元元，设设ord()=s，若若s=q1，则则令令i+1=，算算法法停停止止；否否则转第四步。则转第四步。第第四四步步：寻寻找找ti的的一一个个因因子子d，s的的一一个个因因子子e，使使得得gcd(d,e)=1且且de=lcm(ti,s)。设设，ti+1=lcm(ti,s)。i值加值加1，返

26、回第二步。，返回第二步。第28页/共67页二、本原元二、本原元 注意，在这个算法中：注意，在这个算法中：由由于于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时，可以取时，可以取d=4，e=9。在在第第四四步步中中，元元素素的的阶阶为为ti/gcd

27、(ti,ti/d)=d，的的阶阶为为s/gcd(s,s/e)=e。于于是是这这两两个个元元素素的的乘乘积积的的阶阶为为de=lcm(ti,s)。因因而而在在第第四四步步中中得得到到的的新新的的元元素素i+1的的阶阶ti+1恰恰好是好是ord(i)的一个倍数，因而这个算法最终必定会终止于一个本原元。的一个倍数，因而这个算法最终必定会终止于一个本原元。第29页/共67页二、本原元二、本原元 例例利利用用多多项项式式f(x)=x3+2x+1构构造造一一个个有有限限域域，并并找找出出域中的本原元。域中的本原元。解解：这这里里只只给给出出了了构构造造域域的的多多项项式式，并并未未给给出出构构造造域域所所

28、需需的的欧欧氏氏环环，因因而而可可以以任任意意选选一一个个欧欧氏氏环环，只只要保证要保证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。第30页/共67页二、本原元二、本原元 在域在域F中注意到中注意到x3x+2(mod x3+2x+1)，x4x2+2

29、x(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)接下来利用高斯算法寻找这个域中的本原元。接下来利用高斯算法寻找这个域中的本原元。第31页/共67页二、本原元二、本原元 首首先先取取1=(0,1,0)=x，为为了了计计算算1的的阶阶，先先来来计计算算x的的各个幂次对各个幂次对f(x)取模的结果

30、取模的结果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)第32页/共67页二、本原元二、本原元 x92x3+2xx+1(mod x3+2x+1),x10 x2+x(mod x3+2x+1)x11x3+x2x2+x+2(mod x

31、3+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)第33页/共67页二、本原元二、本原元 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(mo

32、d x3+2x+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=q1=26，算法停止；，算法停止；1就是就是F中的本原元。中的本原元。第34页/共67页二、本原元二、本原元 例例利利用用多多项项式式f(x)=x22构构造造一一个个有有限限域域，并并找找出出这这个个域中的本原元。域中的本原元。解解：这这里里只只给给出出了了构构造造域域的的多多

33、项项式式，并并未未给给出出构构造造域域所所需需的的欧欧氏氏环环，因因而而需需要要选选择择一一个个欧欧氏氏环环，并并保保证证f(x)为此域中的不可约多项式。为此域中的不可约多项式。注意到在注意到在F3中中f(0)=1，f(1)=f(2)=2，因而，因而该多项式是该多项式是F3x中的一个不可约多项式，中的一个不可约多项式，以此可以构造一个具有以此可以构造一个具有9个元素的有限域个元素的有限域F。域域 F中中 的的 元元 素素 都都 可可 以以 看看 做做 是是 二二 维维 向向 量量(a,b)，其其 中中a,b F3=0,1,2。第35页/共67页二、本原元二、本原元 在在域域F中中注注意意到到x

34、22(mod x22)，因因而而可可定定义义域域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 x22),x1x(mod x22),x22(mod x22)x32x(mod x22)，x42x21(m

35、od x22)，第36页/共67页二、本原元二、本原元 因而因而1=(1,0)=x的阶为的阶为4，即在高斯算法中有即在高斯算法中有t1=4。由于由于t1q1=8，因而因而1不是本原元，不是本原元，接着转至第接着转至第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)第37页/共67页二、本原元二、本原元 类似地可以得到

36、类似地可以得到=(1,2)=x+2的的各各个个幂幂次次对对f(x)取取模模的的结结果果的的向量表示向量表示因而因而的阶的阶s=8=q1，则令则令2=，算法停止；算法停止；2就是就是F中的本原元。中的本原元。ii0(0,1)1(1,2)2(1,0)3(2,2)4(0,2)5(2,1)6(2,0)7(1,1)8(0,1)表表64 =(1,2)=x+2的各个的各个幂次的向量表示幂次的向量表示第38页/共67页二、本原元二、本原元 例例在在上上例例中中，由由于于f(x)=x22在在F5中中也也没没有有2的的平平方方根根，因因而而该该多多项项式式也也是是F5x中中的的一一个个不不可可约约多多项项式式，由

37、此也可以构造一个具有由此也可以构造一个具有25个元素的有限域个元素的有限域F如下。如下。首首先先域域F中中的的元元素素都都可可以以看看做做是是二二维维向向量量(a,b)，其其中中a,b F5=0,1,2,3,4。在在域域F中中注注意意到到x22(mod x22)，因因而而可可定定义义域域F中中的的加法与乘法运算如下：加法与乘法运算如下：(a1,b1)+(a2,b2)=(a1+a2,b1+b2)。(a1,b1)+(a2,b2)=(a1b2+a2b1,b1b2+2a1a2)接下来利用高斯算法寻找这个域中的本原元。接下来利用高斯算法寻找这个域中的本原元。第39页/共67页二、本原元二、本原元 首首先

38、先取取1=(1,0)=x，计计算算得得到到1=(1,0)=x的的 各各 个个 幂幂 次次 对对 f(x)取模的结果的向量表示取模的结果的向量表示 因因而而1的的阶阶为为8，即即在在高高斯斯算算法法中中t1=8。由由于于t1q1=24，因因而而1不不是是本本原原元元，接接着着转转至至第第3步步，需需要要选选择择一一个个不不是是1的的幂幂次的元素次的元素，例如可以选例如可以选=(1,1)=x+1，则，则 2=(x+1)2 2x+3(modx22)=(2,3)，类类似似地地可可以以得得到到的的各各个个幂幂次次对对f(x)取取模模的的结结果果的的向向量量表表示示如如下下 i1i0(0,1)1(1,0)

39、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的的各个幂次的向量表示各个幂次的向量表示第40页/共67页二、本原元二、本原元 因而因而的阶为的阶为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)=212+21=2x2+2x2x+4(mod x22)且且

40、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)第41页/共67页三、最小多项式与本原多项式三、最小多项式与本原多项式设设F是是有有pm个个元元素素的的有有限限域域，则则由由前前面面的的讨讨论论F可可以以看看做是做是Fp上的一个上的一个m维向量空间。维向量空间。接下来接下来 F，考察，考察F中的中的m+1个元素个元素1,2,m。

41、由由于于F在在Fp上上的的维维数数为为m，因因而而这这m+1个个元元素素在在Fp上上必必然然是是线线性性相相关关的的，即即存存在在不不全全为为零零的的元元素素a0,a1,am，使得，使得a0+a1+a22+amm=0。即即是多项式方程是多项式方程a(x)=a0+a1x+a2x2+amxm=0的根。的根。当当然然，也也可可以以满满足足其其它它多多项项式式方方程程，因因而而可可以以定定义义S()为所有这样的多项式构成的集合，即为所有这样的多项式构成的集合，即S()=f(x)Fpx:f()=0。第42页/共67页三、最小多项式与本原多项式三、最小多项式与本原多项式设设p(x)为为集集合合S()中中次

42、次数数最最低低的的非非零零多多项项式式，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中中以以为根的为根的最小多项式最小多项式。若要求。若要

43、求p(x)是首一多项式，则是首一多项式，则这样的这样的p(x)是唯一的，并且是不可约多项式是唯一的，并且是不可约多项式。这这是是由由于于，若若p(x)=a(x)b(x)，则则由由于于p()=0，必必然然会会得到得到a()=0或或b()=0，这与，这与deg(p)的最小性相矛盾。的最小性相矛盾。第43页/共67页三、最小多项式与本原多项式三、最小多项式与本原多项式定定理理设设F是是有有pm个个元元素素的的有有限限域域，则则 F，若若Fpx中存在唯一的首一多项式中存在唯一的首一多项式p(x)，使得，使得i.p()=0，ii.deg(p)m，iii.若若f(x)为为Fp(x)中中另另外外一一个个以以

44、为为根根的的多多项项式式，则则p(x)|f(x)。则则称称p(x)为为的的相相对对于于F的的子子域域Fp的的最最小小多多项项式式，若若为为本本原原元元，则则称称其其所所对对应应的的最最小小多多项项式式为为本原多项式。本原多项式。第44页/共67页三、最小多项式与本原多项式三、最小多项式与本原多项式例例计算例所给域中某些个元素的最小多项式。计算例所给域中某些个元素的最小多项式。解解：考虑元素：考虑元素(1,0)的幂次，这里暂时将的幂次，这里暂时将(1,0)记为记为。首首先先0=1，若若F中中的的元元素素就就是是Fp中中的的元元素素，则则其其最最小小多项式将总是多项式将总是x，因而，因而0=1的最

45、小多项式为的最小多项式为x1。接下来，考虑接下来，考虑自身。由于自身。由于不是不是F3中的元素，因而中的元素，因而x也不是也不是F3中的元素。中的元素。然然而而，二二维维向向量量空空间间F中中的的3个个向向量量1=(0,1)，=(1,0)，2=(0,2)必定是线性相关的。必定是线性相关的。进而可以得到一个以进而可以得到一个以为根的二次方程，由于为根的二次方程，由于220=221=0，因而因而的最小多项式为的最小多项式为x22，即定义域的多项式。，即定义域的多项式。第45页/共67页三、最小多项式与本原多项式三、最小多项式与本原多项式接下来计算接下来计算2的最小多项式，由于的最小多项式，由于=2

46、=(0,2)，因而，因而其最小多项式为其最小多项式为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或者为或者为

47、x2+2x+2。第46页/共67页三、最小多项式与本原多项式三、最小多项式与本原多项式以下设以下设F是有限域，是有限域，K是是F的有的有q个元素的子域。个元素的子域。由由前前面面的的讨讨论论知知可可以以将将F看看做做是是K上上的的一一个个向向量量空空间间，故故F中的元素的个数是中的元素的个数是K中的元素个数中的元素个数q的幂次。的幂次。同时同时q应是某个素数应是某个素数p的幂次，即的幂次，即q=pm。因而存在某整数因而存在某整数n，使得，使得|F|=qn=pnm。F，将定理中的素域，将定理中的素域Fp替换为替换为K，则，则可以得到可以得到的相对于域的相对于域K的最小多项式的最小多项式p(x)。

48、为为了了得得到到p(x)的的具具体体表表达达式式，需需要要引引入入如如下下几几个个引引理理第47页/共67页三、最小多项式与本原多项式三、最小多项式与本原多项式引引理理 F，则则 K当当且且仅仅当当q=。特特别别地地，x K，有方程，有方程xqx=0。证明证明：K，若若=0，则，则q=；否则设否则设ord()=t，则则t|(q1)，因而，因而q1=1，故，故q=，即即K中的中的q个元素为方程个元素为方程xqx=0提供了提供了q个不同个不同的解。的解。同时该方程也就只有这同时该方程也就只有这q个解，而无其它解。个解，而无其它解。第48页/共67页三、最小多项式与本原多项式三、最小多项式与本原多项

49、式引理引理 若若p为素数，则对于为素数，则对于1kp1，有，有p整除二项式系数整除二项式系数 。证明证明：由二项式系数的定义有：由二项式系数的定义有该分数的分子被该分数的分子被p整除，但分母不被整除，但分母不被p整除。整除。第49页/共67页三、最小多项式与本原多项式三、最小多项式与本原多项式引理引理设设1,2,t是任意是任意p特征域中的元素，则特征域中的元素，则k=1,2,3,证明证明：首先当：首先当t=1时，结论成立。时，结论成立。当当t=2时，利用数学归纳法证明时，利用数学归纳法证明 k=1,2,3,。若。若k=1，上述等式中的每个二项式系数都是上述等式中的每个二项式系数都是p的倍数，进

50、而在的倍数，进而在p特征域中这些系数都是特征域中这些系数都是0。因而。因而 。第50页/共67页三、最小多项式与本原多项式三、最小多项式与本原多项式若若k=2，则，则因而当因而当k=2时结论成立。时结论成立。以此为基础，由数学归纳法知以此为基础，由数学归纳法知t=2时，等式时，等式 k=1,2,3,，成立。，成立。进而，由数学归纳法知结论成立。进而，由数学归纳法知结论成立。第51页/共67页三、最小多项式与本原多项式三、最小多项式与本原多项式一般有限域中的最小多项式。一般有限域中的最小多项式。首首先先若若Kx中中的的多多项项式式p(x)=p0+p0 x+p2x2+pdxd以以为根，即为根，即p