数论与有限域六课件

第六章第六章 有限域的抽象性质有限域的抽象性质第一节第一节 有限域的加法结构有限域的加法结构 一、域的特征一、域的特征 二、二、有限域有限域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,中的元素中的元素不可能不可能都不相同都不相同，故可故可设存在整数设存在整数c，使得，使得u0=0,u1,u2,uk+c1互不相同且互不相同且uk+c=uk。又又uk+cuk=uc，即即uc=ce=0。因而。因而我们我们找到了一个整数找到了一个整数c，使得，使得ce=0。一般地。一般地 一、域的特征一、域的特征定定义义6.1.1记记有有限限域域F的的乘乘法法单单位位元元为为e，如如果果存存在在正正整整数数n，使使得得ne=0，则则称称满满足足此此条条件件的的最最小小正正整整数数n为为域域F的的特特征征。如如果果这这样样的的正正整整数数不不存存在在，则则称称域域F的的特征为零。特征为零。例例6.1.1 容容易易验验证证由由前前一一章章的的例例5.4.5得得到到的的域域GF(8)的的特特征为征为2，由例由例5.4.4得到域得到域GF(9)的特征为的特征为3，而实数域与有理数域的特征则为而实数域与有理数域的特征则为0。一、域的特征一、域的特征定理定理6.1.1若若F是有限域，则是有限域，则F的特征的特征c必定为素数。必定为素数。证证明明：假假设设相相反反，设设正正整整数数c=ab，其其中中1ac，1bc，则则由由上上述述有有限限域域F中中的的序序列列u0,u1,u2,所所具具有有的的性质知性质知uc=uaub。但但uc=0，而而ua与与ub均均不不为为0，如如此此与与域域中中无无零零因因子子的的性性质相矛盾，因而质相矛盾，因而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=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，则定理得证。，则定理得证。否否则则，我我们们在在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中中的的元元素素可可以以看看做做是是域域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互不相同且互不相同且k=k+t，则，则k=0；否则若否则若k0，则由，则由k=k+t得到得到k1=k+t1，这与这与e,2,k+t1互不相同相矛盾，进而互不相同相矛盾，进而t=e。一般地一般地一、元素的阶一、元素的阶定定义义6.2.1 记记有有限限域域F的的乘乘法法单单位位元元为为e，则则称称使使得得等等式式t=e成立成立的最小正整数的最小正整数t，t1，为，为的阶，记为的阶，记为ord()。通通常常，取取不不同同值值，的的阶阶相相应应地地也也会会有有不不同同的的取取值值，并并且且计计算算有有可可能能也也会会很很困困难难。但但是是，在在域域F中中利利用用以以下下结论可以很明确地确定出结论可以很明确地确定出t，t1，阶元素的个数。，阶元素的个数。一、元素的阶一、元素的阶定定理理6.2.1设设有有限限域域F具具有有q个个元元素素，F*，若若的的阶阶为为t，则，则t|(q1)。证证明明：由由域域的的定定义义，F*构构成成了了乘乘法法群群，由由于于的的阶阶为为t，即即t=e，因因而而e,2,t1构构成成了了F*的的子子群群。拉拉格格朗朗日日定定理理子子群群中中的的元元素素个个数数一一定定会会是是整整个个群群的的元元素素个个数数的的因因子子，因而因而t|(q1)。一、元素的阶一、元素的阶引引理理6.2.1设设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(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)的的次次数数为为m1，由由归归纳纳假假设设方方程程q(x)=0至至多多有有m1个根，因而方程个根，因而方程p(x)=0至多有至多有m个根。个根。一、元素的阶一、元素的阶例例6.2.1设设Z8为整数模为整数模8的剩余类环，即的剩余类环，即定义了模定义了模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中中的的元元素都必定是素都必定是的幂。的幂。证明证明：若：若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=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(i)|(t/d)，就得到，就得到ord(i)=t/d，也即，也即ord(i)=t/gcd(i,t)。一、元素的阶一、元素的阶例例6.2.2设设域域F中中的的元元素素的的阶阶ord()=8，则则利利用用引引理理6.2.2可以计算可以计算i，i=0,1,7的阶的结果如下表：的阶的结果如下表：表表61 域域F中各元素阶列表中各元素阶列表 igcd(i,8)i081118224318442518624718表表61 中有：中有：4个个8阶的元素，阶的元素，2个个4阶的元素，阶的元素，1个个2阶的元素，阶的元素，以及以及1个个1阶的元素；阶的元素；一、元素的阶一、元素的阶定定理理6.2.2设设t为为整整数数，则则在在域域F中中或或者者没没有有t阶阶元元素素，或或者者恰有恰有(t)个个t阶元素。阶元素。证明证明：若在域：若在域F中没有中没有t阶元素，则定理得证。阶元素，则定理得证。反反之之，若若ord()=t，正正如如上上面面所所观观察察到到的的每每个个t阶阶元元素素都都在集合在集合1,2,t1中。中。但是由引理但是由引理6.2.2，i的阶为的阶为t当且仅当当且仅当gcd(t,i)=1。因而这样的因而这样的i恰有恰有(t)个。个。一、元素的阶一、元素的阶到到此此，对对于于有有q个个元元素素的的有有限限域域F的的元元素素的的阶阶我我们们有有这这样样的认识：的认识：1.给定正整数给定正整数t，若，若t(q1)，则在域，则在域F中不存在中不存在t阶元素；阶元素；2.若若t|(q1)，则则在在域域F中中或或者者没没有有t阶阶元元素素，或或者者恰恰有有(t)个个t阶元素。阶元素。接接下下来来我我们们证证明明若若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，与域，与域F中的非零中的非零元素的个数相同。元素的个数相同。一、元素的阶一、元素的阶定理定理6.2.3若若n为正整数，则为正整数，则 。证明证明：设：设Sn为有理数集：为有理数集：，而，而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)。因而结论得证。因而结论得证。一、元素的阶一、元素的阶例例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.4设设F是是有有q个个元元素素的的有有限限域域，t为为正正整整数数。若若t(q1)，则则域域F中不存在中不存在t阶元素；若阶元素；若t|(q1)，则域，则域F中恰有中恰有(t)个个t阶元素。阶元素。证明证明：只需证明：若：只需证明：若t|(q1)，则域，则域F中恰有中恰有(t)个个t阶元素。阶元素。对对于于q1的的每每个个正正因因子子t，记记域域F中中t阶阶元元素素的的个个数数为为(t)。则则由由域域F中的每个非零元素的阶都必定整除中的每个非零元素的阶都必定整除q1，可以得到，可以得到又又 ，进而，进而但但是是对对于于所所有有的的t，(t)(t)0。因因而而对对于于q1的的每每个个正正因因子子t，都都有有(t)=(t)。一、元素的阶一、元素的阶推推论论6.2.2 在在每每个个有有限限域域中中，都都至至少少存存在在一一个个（事事实实上上恰恰有有(q1)个个）q1阶阶元元素素。因因而而任意有限域的乘法群都是循环群。任意有限域的乘法群都是循环群。二、本原元二、本原元 定定义义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，而，而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，因因 而而 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=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，返回第二步。，返回第二步。二、本原元二、本原元 注意，在这个算法中：注意，在这个算法中：由由于于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(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构构造造一一个个有有限限域域，并并找找出出域中的本原元。域中的本原元。解解：这这里里只只给给出出了了构构造造域域的的多多项项式式，并并未未给给出出构构造造域域所所需需的的欧欧氏氏环环，因因而而可可以以任任意意选选一一个个欧欧氏氏环环，只只要要保保证证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+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，为为了了计计算算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+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+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中的本原元。中的本原元。二、本原元二、本原元 例例6.2.7利利用用多多项项式式f(x)=x22构构造造一一个个有有限限域域，并并找找出出这这个域中的本原元。个域中的本原元。解解：这这里里只只给给出出了了构构造造域域的的多多项项式式，并并未未给给出出构构造造域域所所需需的的欧欧氏氏环环，因因而而需需要要选选择择一一个个欧欧氏氏环环，并并保保证证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+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(mod x22)，二、本原元二、本原元 因而因而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)二、本原元二、本原元 类似地可以得到类似地可以得到=(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的各个的各个幂次的向量表示幂次的向量表示二、本原元二、本原元 例例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)，因因而而可可定定义义域域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步步，需需要要选选择择一一个个不不是是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，满满 足足 条条 件件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是是有有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()=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)，则则由由于于p()=0，必必然然会会得得到到a()=0或或b()=0，这与，这与deg(p)的最小性相矛盾。的最小性相矛盾。三、最小多项式与本原多项式三、最小多项式与本原多项式定定理理6.2.5 设设F是是有有pm个个元元素素的的有有限限域域，则则 F，若若Fpx中存在唯一的首一多项式中存在唯一的首一多项式p(x)，使得，使得i.p()=0，ii.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，因而，因而0=1的最小多项式为的最小多项式为x1。接下来，考虑接下来，考虑自身。由于自身。由于不是不是F3中的元素，因而中的元素，因而x也不是也不是F3中的元素。中的元素。然然而而，二二维维向向量量空空间间F中中的的3个个向向量量1=(0,1)，=(1,0)，2=(0,2)必定是线性相关的。必定是线性相关的。进而可以得到一个以进而可以得到一个以为根的二次方程，由于为根的二次方程，由于220=221=0，因而因而的最小多项式为的最小多项式为x22，即定义域的多项式。，即定义域的多项式。三、最小多项式与本原多项式三、最小多项式与本原多项式接下来计算接下来计算2的最小多项式，由于的最小多项式，由于=2=(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或者为或者为x2+2x+2。三、最小多项式与本原多项式三、最小多项式与本原多项式以下设以下设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)的具体表达式，需要引入如下几个引理的具体表达式，需要引入如下几个引理三、最小多项式与本原多项式三、最小多项式与本原多项式引引理理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整除二项式系数整除二项式系数 。证明证明：由二项式系数的定义有：由二项式系数的定义有该分数的分子被该分数的分子被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时结论成立。时结论成立。以此为基础，由数学归纳法知以此为基础，由数学归纳法知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)的的根根。利利用用同同样样的的推推导过程，我们会发现导过程，我们会发现,等等也都是等等也都是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，则，则三、最小多项式与本原多项式三、最小多项式与本原多项式证证明明：假假设设0，则则由由于于相相对对于于子子域域K的的的的各各共共轭轭根根都都是是有有限限域域F中中的的元元素素，因因而而序序列列,q,中中必必定定会会出现重复。出现重复。设设 为为序序列列,q,中中最最先先出出现现重重复复的的元元素素，且且 ，其中，其中jd，则，则 因而因而ord()|qj(qd-j1)。但但ord()|(qn1)，即即gcd(ord(),qj)=1。因而。因而ord()|(qd-j1)，即即 ，也也即即 也也是是出出现现了了重重复复的的元元素素，但但是是最最先出现重复的元素。因而先出现重复的元素。因而j=0，即，即三、最小多项式与本原多项式三、最小多项式与本原多项式但但F中有中有qn个元素，因而个元素，因而因因而而 。由由于于 是是最最先先出出现现重重复复的的元元素素，因而必定有因而必定有gcd(d,n)=d，即，即d是是n的一个因子。的一个因子。因而因而的不同共轭根的个数是的不同共轭根的个数是n的一个因子。的一个因子。同同时时，通通过过前前面面的的讨讨论论，发发现现d是是满满足足式式qd1(mod t)的的最小正整数，其中最小正整数，其中t=ord()。综合以上讨论知结论成立。综合以上讨论知结论成立。三、最小多项式与本原多项式三、最小多项式与本原多项式由由定定理理6.2.6相相对对于于子子域域K的的共共轭轭根根系系中中的的d个个元元素素,q,必必定定都都是是的的最最小小多多项项式式的的根根。因因而而若若定定义义多多项项式式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)=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)，它它是是的的最最小小多多项项式式的的一个因式，且其系数都在子域一个因式，且其系数都在子域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)(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+115000111x+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互互为为共共轭轭根根，因因而而他他们们具具有有相相同同的的最最小小多多项项式式。进进而而由由的的最最小小多多项项式式为为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个个幂幂次次中中必必然然存存在在一一个个线线性性关关系系式式。下下面面再再介介绍绍一一个个上上述述方方法法的的变变形形。这这里里我我们们暂暂时时记记3=，则则通通过过计计算算可可以得到以得到3=的最初的最初5个幂次依次为个幂次依次为 1=0001=3=10002=6=11003=9=10104=12=1111三、最小多项式与本原多项式三、最小多项式与本原多项式下下面面我我们们通通过过基基本本的的列列变变换换找找出出这这5个个四四维维向向量量的的一一个个线线性性相相关关关关系式。首先将第二列加到第一列，得到系式。首先将第二列加到第一列，得到00011000010010100111 接着将第三列加到第一列，得到接着将第三列加到第一列，得到00011000010000101111三、最小多项式与本原多项式三、最小多项式与本原多项式i=4：由由于于,2,4,8互互为为共共轭轭根根，因因而而他他们们具具有有相相同同的的最最小小多多项项式式。进进而而由由的的最最小小多多项项式式为为x4+x+1，可知可知4的最小多项式也是的最小多项式也是x4+x+1。i=5：由由于于5的的最最小小多多项项式式为为(x5)(x10)，将将其其完完全全展开得到展开得到(x5)(x10)=x25x10 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=，则则通通过过计计算算可可以以得得到到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。当当然然我我们们也也可可以以将将式式(x7)(x14)(x13)(x11)完完全全展展开开以便证明以便证明7的最小多项式为的最小多项式为x4+x3+1。