数论与有限域 第六章

1、第六章第六章 有限域的抽象性质有限域的抽象性质第一节第一节 有限域的加法结构有限域的加法结构 一、域的特征一、域的特征 二、二、有限域有限域F F中的元素个数中的元素个数 一、域的特征一、域的特征设设e为有限域为有限域F中的乘法单位元。定义中的乘法单位元。定义F中的序列中的序列u0, u1, u2,如下如下u0=0, un=un-1+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是有限域是有限域，因而序列因

2、而序列u0, u1, u2,中的元素中的元素不可能不可能都不相同都不相同，故可故可设存在整数设存在整数c，使得，使得u0=0, u1, u2, uk+c-1互不相同且互不相同且uk+c=uk。又又uk+c-uk=uc，即即uc=ce=0。因。因而而我们我们找到了一个整数找到了一个整数c，使得，使得ce=0。一般地。一般地 一、域的特征一、域的特征定义定义6.1.1记有限域记有限域F的乘法单位元为的乘法单位元为e，如果存在正整，如果存在正整数数n，使得，使得ne=0，则称满足此条件的最小正整数，则称满足此条件的最小正整数n为为域域F的特征。如果这样的正整数不存在，则称域的特征。如果这样的正整数不

3、存在，则称域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，而，而

4、ua与与ub均不为均不为0，如此与域中无零因子的性，如此与域中无零因子的性质相矛盾，因而质相矛盾，因而c必定为素数。必定为素数。在以下的叙述中，记有限域的特征为字母在以下的叙述中，记有限域的特征为字母p，则易知序，则易知序列列u0, u1, u2,中第一个出现重复的元素中第一个出现重复的元素是是up=0，进而进而u0, u1, u2, up-1互不相同。互不相同。二、二、有限域有限域F F中的元素个数中的元素个数定理定理6.1.2有限域有限域F中的元素个数中的元素个数q必定是某个素数必定是某个素数p的幂的幂次，即次，即q=pm。证明证明：首先，容易验证域：首先，容易验证域F的子集的子集u0,

5、u1, u2, up-1构构成了成了F的一个子域，记为的一个子域，记为Fp。若若F=Fp，则，则q=p，结论得证。，结论得证。否则否则设设1 F-Fp，则，则 a, b Fp，在，在F中都可以对应地找中都可以对应地找到一个元素到一个元素a1+b，显然在，显然在F中共有中共有p2个元素具有这个元素具有这样的形式，因而若域样的形式，因而若域F中元素的数目中元素的数目q=p2，则定理得，则定理得证。证。二、二、有限域有限域F F中的元素个数中的元素个数否则否则在在F中选择不具有形式中选择不具有形式a1+b的元素的元素2，则，则 a, b, c Fp，在，在F中都可以对应地找到一个元素中都可以对应地找

6、到一个元素a2+b1+c，显然在显然在F中共有中共有p3个元素具有此形式，因而若域个元素具有此形式，因而若域F中中元素的数目元素的数目q=p3，则定理得证。，则定理得证。 否则否则，我们在，我们在F中选择不具有形式中选择不具有形式a2+b1+c的元素的元素3，。最终最终，在，在F中中可以可以选定一组元素选定一组元素1,2,m-1，使得，使得F中 的 每 个 元 素中 的 每 个 元 素 都 有 唯 一 的 表 达 式 ：都 有 唯 一 的 表 达 式 ：=a1+a21+a32+am-1m-1，其中，其中ai Fp，i=1, 2, , m-1。由于每个。由于每个ai有有p个可能的取值，因而个可能

7、的取值，因而F中恰有中恰有pm个元素。定理得证个元素。定理得证 二、二、有限域有限域F F中的元素个数中的元素个数通过定理通过定理6.1.2，对有限域，对有限域F的加法结构我们可以得到如的加法结构我们可以得到如下认识：下认识：有限域有限域F中的元素可以看做是域中的元素可以看做是域Fp中元素构成的中元素构成的m元组，元组，且且(a1, a2,am)+(b1,b2,bm)=(a1b1, a2+b2, am+bm)接下来，我们来研究域接下来，我们来研究域F的乘法结构。的乘法结构。 第二节第二节 有限域的乘法结构有限域的乘法结构 一、元素的阶一、元素的阶二、本原元二、本原元 三、最小多项式与本原多项式

8、三、最小多项式与本原多项式一、元素的阶一、元素的阶以下设以下设F为有限域，为有限域，F*为有限域为有限域F中的所有非零元素构成中的所有非零元素构成的集合，的集合， F*，考察由考察由的各个幂次所构成的序列的各个幂次所构成的序列e, , 2, n,的性质。的性质。 首先由域首先由域F对乘法运算的封闭性，知对乘法运算的封闭性，知 i，i F，又又F是有限域，因而序列是有限域，因而序列e, , 2, n,中必然会出现重中必然会出现重复。复。 设设e, , 2, k+t-1互不相同且互不相同且k=k+t，则，则k=0；否则若否则若k0，则由，则由k=k+t得到得到k-1=k+t-1，这与这与e, ,

9、2, k+t-1互不相同相矛盾，进而互不相同相矛盾，进而t=e。一般地一般地一、元素的阶一、元素的阶定义定义6.2.1 记有限域记有限域F的乘法单位元为的乘法单位元为e，则称使得等式，则称使得等式t=e成立成立的最小正整数的最小正整数t，t1，为，为的阶，记为的阶，记为ord()。 通常，通常，取不同值，取不同值，的阶相应地也会有不同的取值，的阶相应地也会有不同的取值，并且计算有可能也会很困难。但是，在域并且计算有可能也会很困难。但是，在域F中利用以中利用以下结论可以很明确地确定出下结论可以很明确地确定出t，t1，阶元素的个数。，阶元素的个数。一、元素的阶一、元素的阶定理定理6.2.1设有限域

10、设有限域F具有具有q个元素，个元素， F*，若若的阶为的阶为t，则则t|(q-1)。证明证明：由域的定义，：由域的定义，F*构成了乘法群，由于构成了乘法群，由于的阶为的阶为t，即即t=e，因而因而e, , 2, t-1构成了构成了F*的子群。拉格朗日定理子的子群。拉格朗日定理子群中的元素个数一定会是整个群的元素个数的因子，群中的元素个数一定会是整个群的元素个数的因子，因而因而t|(q-1)。一、元素的阶一、元素的阶引理引理6.2.1设设F为有限域，若为有限域，若p(x)是是Fx中的中的m次多项式，次多项式，则在域则在域F中方程中方程p(x)=0至多有至多有m个不同的根。个不同的根。证明证明：对

11、：对m进行数学归纳。进行数学归纳。若若m=1，此时，此时p(x)为一次多项式，即方程为一次多项式，即方程p(x)=0具有形式具有形式ax+b=0，显然该方程只有一个根，显然该方程只有一个根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中的常数多项式，也即域中的

12、常数多项式，也即域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-1个根，因而方程个根，因而方程p(x)=0至多有至多有m个根。个根。 一、元素的阶一、元素的阶例例6.2.1设设Z8为整数模为整数模8的剩余类环，即的剩余

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

14、元中的元素都必定是素都必定是的幂。的幂。证明证明：若：若ord()=t，即，即t=e，则，则(i)t-e=(t)i-e=0，即即t个元素个元素e, , 2, t-1是方程是方程xt-e=0的的t个不同的根，而个不同的根，而由引理由引理6.2.1该方程不会再有其它的根！即该方程不会再有其它的根！即每个满足方程每个满足方程xt=e的域的域F中的元素都必定是中的元素都必定是的幂。的幂。但是正如下面的引理但是正如下面的引理6.2.2所述的，并不是所述的，并不是的每个幂次都的每个幂次都有阶有阶t。 一、元素的阶一、元素的阶引理引理6.2.2若若ord()=t，则，则ord(i)=t/gcd(i,t)。证

15、明证明：首先，易知：首先，易知 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，也即

16、，也即ord(i)=t/gcd(i,t)。一、元素的阶一、元素的阶例例6.2.2设域设域F中的元素中的元素的阶的阶ord()=8，则利用引理，则利用引理6.2.2可以计算可以计算i ，i=0, 1,7的阶的结果如下表：的阶的结果如下表： 表表6-1 域域F中各元素阶列表中各元素阶列表 igcd(i,8)i081118224318442518624718表表6-1 中有：中有：4个个8阶的元素，阶的元素，2个个4阶的元素，阶的元素，1个个2阶的元素，阶的元素，以及以及1个个1阶的元素；阶的元素；一、元素的阶一、元素的阶定理定理6.2.2设设t为整数，则在域为整数，则在域F中或者没有中或者没有t阶

17、元素，或者阶元素，或者恰有恰有(t)个个t阶元素。阶元素。证明证明：若在域：若在域F中没有中没有t阶元素，则定理得证。阶元素，则定理得证。反之，若反之，若ord()=t，正如上面所观察到的每个，正如上面所观察到的每个t阶元素都阶元素都在集合在集合1, , 2, t-1中。中。但是由引理但是由引理6.2.2，i的阶为的阶为t当且仅当当且仅当gcd(t,i)=1。因而这样的因而这样的i恰有恰有(t)个。个。一、元素的阶一、元素的阶到此，对于有到此，对于有q个元素的有限域个元素的有限域F的元素的阶我们有这样的元素的阶我们有这样的认识：的认识：1.给定正整数给定正整数t，若，若t (q-1)，则在域，

18、则在域F中不存在中不存在t阶元素；阶元素；2.若若t|(q-1)，则在域，则在域F中或者没有中或者没有t阶元素，或者恰有阶元素，或者恰有(t)个个t阶元素。阶元素。接下来我们证明若接下来我们证明若t确实整除确实整除q-1，则在域，则在域F中将总是存在中将总是存在有有(t)个个t阶元素。在给出具体证明之前，再来看另外阶元素。在给出具体证明之前，再来看另外一个例子。一个例子。一、元素的阶一、元素的阶例例6.2.3设设q=9，则，则q-1=8，进而，进而t的可能取值为的可能取值为1，2，4，8。又对于又对于t的每一个可能取值，的每一个可能取值，t阶元素的个数或者阶元素的个数或者为为0或者为或者为(t

19、)个。个。由欧拉函数的性质，计算得到由欧拉函数的性质，计算得到t和和(t)的取值如下表：的取值如下表：t(t)11214284注：注：(t)列的和为列的和为8，与域与域F中的非零元中的非零元素的个数相同。素的个数相同。 一、元素的阶一、元素的阶定理定理6.2.3若若n为正整数，则为正整数，则 。证明证明：设：设Sn为有理数集：为有理数集： ，而，而Tn为为Sn中的既约分数构成的集合，即中的既约分数构成的集合，即Tn中的元素的分母为中的元素的分母为n，分子与，分子与n相对互素，则相对互素，则|Sn|=n且且|Tn|=(n) (例如例如 且且 )。 ndnd|)( ,2,1nnnnSn 86,82

20、,818 S878583,818， T一、元素的阶一、元素的阶接下来若设集合接下来若设集合Sn中的所有分数都已进行了约简，则中的所有分数都已进行了约简，则集合集合Sn中的每一个分数的分母中的每一个分数的分母d是是n的因子，的因子，其分子其分子e是与是与n相对互素且介于区间相对互素且介于区间1ed的整数。的整数。反之，若反之，若d是是n的正因子，的正因子，1ed，且，且(e,d)=1，则，则分数分数e/d必是集合必是集合Sn中某个分数的约简形式。中某个分数的约简形式。进而，对于进而，对于n的所有因子的所有因子d，Sn将会分解为若干不相交的将会分解为若干不相交的集合集合Td的并集，的并集，即即 ，

21、进而，进而 。同时由于同时由于|Sn|=n，|Td|=(d)。因而结论得证。因而结论得证。 nddnTS| nddnTS|一、元素的阶一、元素的阶例例6.2.4计算计算(35)。解解：按照欧拉函数的定义，可以在：按照欧拉函数的定义，可以在1，2，3，35中中逐个测试其是否与逐个测试其是否与35相对互素。相对互素。然而，由定理然而，由定理6.2.3应有应有(1)+(5)+(7)+(35)=35，同时，同时，(1)=1，(5)=4，(7)=6，因而因而(35)=35-1-4-6=24。 一、元素的阶一、元素的阶定理定理6.2.4设设F是有是有q个元素的有限域，个元素的有限域，t为正整数。若为正整数

22、。若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)。 1)()1(

23、 | qtqt 1|0)()(qttt 1|1)(qtqt 一、元素的阶一、元素的阶推论推论6.2.2 在每个有限域中，都至少存在一个在每个有限域中，都至少存在一个（事实上恰有（事实上恰有(q-1)个）个）q-1阶元素。因而阶元素。因而任意有限域的乘法群都是循环群。任意有限域的乘法群都是循环群。 二、本原元二、本原元 定义定义6.2.1称有限域称有限域F中阶为中阶为q-1的元素，即循环群的元素，即循环群F*=F-0的生成元，为本原元。的生成元，为本原元。例例6.2.5给出域给出域F=Z5以及域以及域F=Z7中的本原元。中的本原元。解解：首先由上节的定理：首先由上节的定理6.2.4，域，域F=Z

24、5中恰有中恰有(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中的元素为

25、中的元素为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，

26、取域，取域F中的任意一个非零元中的任意一个非零元1，且记，且记ord(1)=t1。第二步：若第二步：若ti=q-1，则算法停止：，则算法停止：i即为所寻找的本原元；即为所寻找的本原元；否则转第三步。否则转第三步。第三步：在域第三步：在域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，返回第

27、二步。返回第二步。二、本原元二、本原元 注意，在这个算法中：注意，在这个算法中： 由于由于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,

28、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构造一个有限域，并找出构造一个有限域，并找出域中的本原元。域中的本原元。解解：这里只给出了构造域的多项式，并未给出构造域所：这里只给出了构造域的多项式，并未给出构造域所需的

29、欧氏环，因而可以任意选一个欧氏环，只要保需的欧氏环，因而可以任意选一个欧氏环，只要保证证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 (

30、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)取模的结果取模的结果x0

31、1 (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 x

32、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)二、本原元二、本原元 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

33、(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=q-1=26，算法停止；，算法停止；1就是就是F中的本原元。中的本原元。二、本原元二、本原元 例例6.2.7利用多项式利用多项式f(x)=x2-2构造一个有限域，并找出这构造一个有限域，并找出这个域中的本原元。个域中的本原元。解解：这里只给出了构造域的多项式，并

34、未给出构造域所：这里只给出了构造域的多项式，并未给出构造域所需的欧氏环，因而需要选择一个欧氏环，并保证需的欧氏环，因而需要选择一个欧氏环，并保证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 x2-

35、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 x2-2)，x42x21(mod x2-

36、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各个各个幂次的向量表示幂次的向量表示 i1i0(0,1)1(1,0)2(0,2)3(2,0)4(0,1)二、本原元二、本原元 类似地可以得到类似地可以得到=(1,2)=x+2的各

37、个幂次对的各个幂次对f(x)取模的结果的向取模的结果的向量表示量表示因而因而的阶的阶s=8=q-1，则令则令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)表表6-4 =(1,2)=x+2的各个的各个幂次的向量表示幂次的向量表示二、本原元二、本原元 例例6.2.8 在上例中，由于在上例中，由于f(x)=x2-2在在F5中也没有中也没有2的平方根，的平方根，因而该多项式也是因而该多项式也是F5x中的一个不可约多项式，由中的一个不可约多项式，由此也可以构造一个具有此也可以构

38、造一个具有25个元素的有限域个元素的有限域F如下。如下。首先域首先域F中的元素都可以看做是二维向量中的元素都可以看做是二维向量(a,b)，其中，其中a,b F5=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，计算得到，计

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

40、4)5(4,0)6(0,3)7(3,0)8(0,1)表表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)=212+21=2x2+2x2x+4(mod x2-2)且且2的阶为的阶为lcm(8,12)=24。因而。因而t2=

41、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个元素

42、在个元素在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()中

43、的任意多项式。则由带余数除法，可以找到多中的任意多项式。则由带余数除法，可以找到多项式项式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

44、(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)

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

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

47、小多项式为x-2。接下来计算接下来计算=3的最小多项式，首先计算得到它的三个幂的最小多项式，首先计算得到它的三个幂次如下次如下0=1=(0,1)，=3=(2,0)，2=6=(0,2)，由于由于2=20，因而，因而的最小多项式为的最小多项式为x2-2或者为或者为x2+1。接下来计算本原元接下来计算本原元=(1,2)=x+2的最小多项式。首先计算得的最小多项式。首先计算得到它的三个幂次如下到它的三个幂次如下0=1=(0,1)，=(1,2)，2=(x+2)2x(mod x2-2)=(1,0)，由于由于2=+0，因而，因而的最小多项式为的最小多项式为x2-x-1或者为或者为x2+2x+2。三、最小多项

48、式与本原多项式三、最小多项式与本原多项式以下设以下设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)的具体表

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

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

51、都是p的倍数，进而在的倍数，进而在p特特征域中这些系数都是征域中这些系数都是0。因而。因而 。kkkkptpppt 2121)(kkkppp )(pppppppp 1111)(ppp )(三、最小多项式与本原多项式三、最小多项式与本原多项式若若k=2，则，则因而当因而当k=2时结论成立。时结论成立。以此为基础，由数学归纳法知以此为基础，由数学归纳法知t=2时，等式时，等式 k=1,2,3,，成立。，成立。进而，由数学归纳法知结论成立。进而，由数学归纳法知结论成立。222)()()(pppppppp kkkppp )(三、最小多项式与本原多项式三、最小多项式与本原多项式一般有限域中的最小多项式。

52、一般有限域中的最小多项式。首先若首先若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

53、.2 称称，q，, 为为相对于子域相对于子域K的共轭根系，的共轭根系，并称此共轭根系中的元素个数为并称此共轭根系中的元素个数为的次数，记为的次数，记为deg()。定理定理6.2.6 设设F是有是有qn个元素的有限域，则个元素的有限域，则 F，若，若相相对于子域对于子域K的共轭根系中的元素个数为的共轭根系中的元素个数为d，则，则d|n且且d是满足同余式是满足同余式qd1(modt) 的最小正整数，其中的最小正整数，其中t=ord()。同时。同时 t，若，若t=d+r，且，且0rd-1，则，则rtqq 三、最小多项式与本原多项式三、最小多项式与本原多项式证明证明：假设：假设0，则由于，则由于相对于

54、子域相对于子域K的的各共轭根都的的各共轭根都是有限域是有限域F中的元素，因而序列中的元素，因而序列, q, , 中必定会中必定会出现重复。出现重复。 设设 为序列为序列, q, , 中最先出现重复的元素，中最先出现重复的元素，且且 ，其中，其中jd，则，则 因而因而ord()|qj(qd-j-1)。但但ord()|(qn-1)，即即gcd(ord(), qj)=1。因而。因而ord()|(qd-j-1)，即即 ，也即，也即 也是出现了重复的元素，但是最也是出现了重复的元素，但是最先出现重复的元素。因而先出现重复的元素。因而j=0，即，即2q 2q dq jdqq )1( jdjjdqqqqe

55、jdqjdq dq dq三、最小多项式与本原多项式三、最小多项式与本原多项式但但F中有中有qn个元素，因而个元素，因而因而因而 。由于。由于 是最先出现重复的元素，因是最先出现重复的元素，因而必定有而必定有gcd(d,n)=d，即，即d是是n的一个因子。的一个因子。因而因而的不同共轭根的个数是的不同共轭根的个数是n的一个因子。的一个因子。同时，通过前面的讨论，发现同时，通过前面的讨论，发现d是满足式是满足式qd1(mod t) 的的最小正整数，其中最小正整数，其中t=ord()。综合以上讨论知结论成立。综合以上讨论知结论成立。 nq ),gcd(ndqdq 三、最小多项式与本原多项式三、最小多

56、项式与本原多项式由定理由定理6.2.6相对于子域相对于子域K的共轭根系中的的共轭根系中的d个元素个元素, q, , ,必定都是必定都是的最小多项式的根。因而若定义多的最小多项式的根。因而若定义多项式项式f(x)=(x-)(x-q)(x-) (x-)，则多项式则多项式f(x)必定是必定是的最小多项式的一个因式。的最小多项式的一个因式。并且并且定理定理6.2.7设有限域设有限域F有有qn个元素，个元素，K是是F的一个有的一个有q个元素个元素的子域。则的子域。则 F，相对于子域相对于子域K的最小多项式为的最小多项式为f(x)=(x-)(x-q)(x-) (x-)其中其中d=deg()，即，即相对于子

57、域相对于子域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-q，因而，因而f(x)q=(xq-q)(xq-)(xq-)(xq-)=f(xq)三、最小多项式与本原多项式三、最小多项式与本原多项式但由但由f(x)的展开式应有的展开

58、式应有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中的不可约多项中的不可约多项式。利用

59、此多项式可以构造一个具有式。利用此多项式可以构造一个具有16个元素的域个元素的域F16。若记。若记=x mod x4+x+1，即向量，即向量(0,0,1,0)所对应所对应的域元素，则通过计算可以得到如下运算表的域元素，则通过计算可以得到如下运算表iideg(i)deg()最小多项式最小多项式0000111x+110010154(x-)(x-2)(x-4)(x-8)= x4+x+120100154x4+x+13100054(x-3)(x-6)(x-12) (x-9)= x4+x3+x2+x+140011154x4+x+1iideg(i)deg()最小多项式最小多项式5011032(x-5)(x-10)=x2+x+16110054x4+x3+x2+x+171011154(x-7)(x-14)(x-13) (x-11)= x4+x3+18