第4章 数学理论基础课件.ppt

《第4章 数学理论基础课件.ppt》由会员分享，可在线阅读，更多相关《第4章 数学理论基础课件.ppt（137页珍藏版）》请在三一办公上搜索。

1、,第4章数学理论基础,4.1素数 4.2模运算及Euler定理 4.3群、 域及环 4.4多项式环、 域及群 4.5线性空间及子空间,4.1素数4.1.1基本概念1.素数定义正整数分为素数、合数与1。一个除了能够被1和它本身整除之外，不能被其他任何整数整除的整数，称为素数，也称之为质数。比如2、3、5、7、13、4999都是素数。一般素数用p表示。一个整数除了能够被1和它本身整除之外，还能够被其他整数整除，那么该整数称之为合数。,如果数a能够被b整除，称b是a的一个因子，或称a有一个因子b，记作,ba,(41),如果b是素数，称a有素因子b。设整数n2，有整数a1,a2,an和d，并且有,da

2、1, da2, ,dan,（42）,那么称d为a1,a2,an的公因子,公因子中最大的一个称之为最大公因子,通常记a、b的最大公因子为,gcd(a,b),(43),例如gcd(36，24)=12，gcd(1008，1260，882，1134)=126。设整数n2，有整数a1,a2,an和m，并且有,a1m,a2m,anm,（44）,那么称m为a1,a2,an公倍数,公倍数中最小的一个称之为最小公倍数。显然，公倍数有无穷多个。记a,b的最小公倍数为,lcm(a,b),(45),例如lcm(12，18)=36，lcm(198，240，360)=7920。,那么，可以容易地得到结果：,如果两个整数a

3、1,b1，有gcd(a,b)=1，就称为a、b互素。,2.特殊素数素数中有一些特殊的种类，因具有独特的结构易于攻击者分析，一般在密码算法中应该避免使用。1)孪生素数孪生素数指差值为2的两个素数。因为除2之外，任何素数都不为偶数，当然其差必须大于等于2。例如：3和5，5和7，11和13，29和31，71和73，101和103等。,2)梅森素数把形如Mp=2p-1的素数称为梅森(MMersenne)素数。例如当p=2，3，5，7，13，17，19，31，61，89，107，127等时，Mp就是梅森素数。梅森素数的获取在计算机出现之前是非常困难的，自计算机出现之后情况有所改观。1999年，美国一个青

4、年在网络上利用计算机得到了第38个梅森素数，这也是当时发现的最大的一个素数，它是M6972593=26972593-1，随后，又有人得到了第39个梅森素数，即M13466917。,3)强素数 所谓强素数，是指两个素数p和q，它们满足以下特性：(1)gcd(p-1)，(q-1)应该较小；(2)(p-1)有大的素因子p，(q-1)也有大的素因子q；(3)(p1)和(q1)都有大的素因子；(4)(p+1)和(q+1)都应有大的素因子；(5)(p1)2，(q1)2都应该是素数。做这样的规定，是因为对于当n=pq时，要分解n使用某些特殊的因子分解方式是无效的。当然，对于目前较新的因子分解成果，有无强素数

5、条件限定对其分解效率改变不大。,4.1.2 素数的分布 素数的分布极不均匀，素数越大，分布越稀疏。假设正整数中只有k是个素数，设为p1，p2，pk。令np1p2pk+1，则n1。如果n是素数，则显然与p1，p2，pk都不相同，这与只有k个素数的假设相矛盾。如果n不是素数，则一定有一个素因子，i1，2，否则由于pp1p2pk以及pn，所以p1，这与p是素数相矛盾。故p与p1，p2，pk都不相同，这与只有k个素数的假设相矛盾。因此，素数有无穷多个。,设x0，(x)为不大于x的素数的个数，则,（46）,根据式（46），当x充分大时，有,（47）,4.2模运算及Euler定理 4.2.1基本模运算如果

6、a是整数，n是正整数，则定义a除以n所得的余数为a模n。记作amodn (48)设a、b、m都是整数,如果m|(a-b),则称a和b模m同余,记作ab(modm) (49)同余在数论中是一个最基本的概念，可使用模运算来定义。例如：152(mod13)，734(mod23)，21-9(mod10)。,1模运算符的性质(1)(a mod n)=(b mod n)等价于ab(mod n)；(2)如果n|(a-b),那么ab(mod n)；(3)ab(mod n)等价于ba(mod n)；(4)ab(mod n)和bc(mod n)等价于ac(mod n)。模运算符的性质可以根据模定义直接得到，这里只

7、证明第（2）条。如果n|(a-b),那么存在某个k使得(a-b)=kn，可知a=b+kn。因此，(a mod n)=(b+kn除以n的余数)=（b除以n的余数）=(b mod n)。由模定义知，（amodn）运算将所有的整数映射到0，1，n-1组成的集合。于是出现了能否限制在这个集合上进行算术运算的问题。答案是肯定的，而这种技术被称为模算术。,2.模算术的性质(1)(amodn)+(bmodn)modn=(a+b)modn；(2)(amodn)-(bmodn)modn=(a-b)modn；(3)(amodn)(bmodn)modn=(ab)modn。以上性质的证明非常简单，从其定义就可以直接得

8、到。这里只证明第(1)条。,定义(a mod n)=ra,(b mod n)=rb,于是存在整数j和k,使得a=ra+jn,b=rb+kn。那么有：,(a +b) mod n=（ra + jn + rb + kn）mod n =( ra + rb +(k+j)n) mod n =( ra + rb) mod n =(a mod n)+ (b mod n) mod n,定义比n小的非负整数集合为Zn,则这个集合称为剩余集或模n的剩余类，即,Zn =0，1，(n-1) 或 Zn=a Z1an-1,式中:Z表示全体整数。,设模n的剩余类中与n互素的集合为Z*n，则,（411）,特别是当n为素数时，有

9、Z*n=Zn。,3.模运算的性质模运算满足交换律、结合律、分配律，并存在加法逆元，以及在加法与乘法运算下的恒等性。(1)交换律：,(2)结合律：,(w+ x)+ymod n=w+(x+ y)mod n(wx)ymod n= w(xy)mod n,(3)分配律:,w(x+ y)mod n=(wx)+ (wy)mod n,(4)恒等性质:,(0+w)mod n=w mod n(1w)mod n=w mod n,(5) 存在加法逆元:对于Zn中的任意w,存在一个z,使得:w+z0(mod n)称z为w的加法逆元，并记作-w,且,-w,z=-w,4同余的性质(1)若ab(mod m)，cd(mod m

10、)，则acbd(modm)，acbd(mod m)；(2)若acbc(modm)，gcd(c，m)=1，则ab(mod m)；(3)若acbc(modm)，gcd(c，m)=d，则ab(mod(md)；(4)若ab(modm)，k0，则akbk(modnk)；(5)若ab(modm)，d|gcd（a，b，m）,则a/db/d(modn/d)；(6)若ab(modm),d|m,则ab(modd)；(7)若ab(modm),则gcd(a,m)=gcd(b,m)。,5.模n求逆元的算法设n和u都是整数，且un，n0。若存在一个整数v,0vn，使,成立，则u模n的逆元就是v。,【例41】求13模35的

11、逆元。解因为,所以13模35的逆元为(-8)mod3527。,【例42】计算322 mod 12。解,4.2.2Euler函数及相关定理定理41(中国剩余定理)设m1,m2,mr是两两互素的正整数,a1,a2,ar是整数,则同余方程组为,xai（modmi）(i=1，2，,r),(413),模M=m1,m2,mr有惟一解:,(414),式中：Mi=M/mi,yi=M-1imod mi(i=1,2,r)。,【例43】求解,再计算yi:,则,设n是一个正整数,定义,(415),为Euler函数。Euler函数是定义在正整数集合上的函数。显然, (n)为小于n且与n互素的非负整数的个数。由定义可以立

12、即得出，如果p是一个素数，则(p)p-1，（1）=1是显然的。,定理42如果n1和n2互素，则,(416),证明对任意的0 xn1n2，设,(0r1n1),（4-17）,（4-18）,r1和r2实际上就是用n1和n2分别除x所得的余数。显然，给定x，则可以惟一确定r1和r2 。反过来，给定r1和r2 ，则根据中国剩余定理可以惟一确定x。因此，x与数对(r1和r2)是一一对应的。,因为n1和n2互素，所以x与n1和n2互素，当且仅当x与n1和n2都互素。x与n1和n2都互素当且仅当r1与n1互素并且r2与n2互素。因此，与n1和n2互素的数x的个数等于数对(r1,r2)的个数，其中r1与n1互素

13、，r2与n2互素。因为与n1互素的数r1的个数为(n1)，与n2互素的数r2的个数为(n2)，所以与n1 n2 互素的数x的个数为(n1)(n2)，即(n1n2)=(n1)(n2)。证毕,定理43如果,(419),式中: 为素数;为正整数，则,(420),定理44(Euler定理)设x和n都是正整数，如果gcd(x，n)=1，则,(421),证明设(n)k;r1,r2,rk(0r1,r2,rkn)互不相同且都与n互素。因为x与n互素，所以xr1,xr2,xrk也都与n互素。如果,则必然有,(423),这与假设相矛盾。因此，xr1,xr2,xrk模n两两不同余，即,(424),于是，因为r1,r

14、2,rk都与n互素，所以xk1(mod n)。证毕Euler定理的另一种有用的表达形式为,(425),(426),推论41 (Fermat定理)设x和p都是正整数。如果p是素数且gcd（x，p）1，则,(427),定理45(Fermat定理)设x和p都是正整数。如果p是素数，则,(428),证明因为p是素数，所以x或者与p互素,或者是p的倍数。如果x与p互素，则由推论41知结论显然成立。如果x是p的倍数,则xp也是p的倍数。因此，xp x(mod p)0(mod p)，则结论也成立。 证毕,定理46设n是一个正整数，Zn=0,1,2,n-1，对于uZn，存在vZn使得uv modn=1的充分必

15、要条件是,(429),证明(1)必要性。显然，对任意bZn存在整数q,使得0bu-qnn,即,(430),假设gcd(u，n)1。因为gcd(u,n)|(bu-qn)，所以bu mod n1，即对任意bZn，都有bu mod n1。因此，如果存在vZn使得uv mod n=1，则必然有gcd(u，n)1。,(2)充分性。假设gcd(u,n)=1，则存在整数a和b使得,(431),于是，,au mod n=1,(432),令v=a mod n则,(433),证毕,4.3群、域及环,在群定义中，G的运算“”可以是通常的加法或乘法。若为乘法，则常称e为单位元；若为加法，单位元常记为0，而逆元记为-a

16、。在以后不致引起错误的情况下，运算符“”省略不写，即把ab写作ab。群中元素的个数称之为群的阶或元数。如果群的元数为有限值，则称为有限群；否则称为无限群。在群G中，对任意a，bG都有ab=ba，则称G为Abel群、交换群、加法群或可换群。,一个非空集合S，仅仅满足群定义中的条件(1)和条件(2)，即运算满足封闭性和结合律，则称S为半群(Semigroup)。一个非空集合M，仅仅满足群定义中的条件(1)、条件(2)和条件(3)，即运算满足封闭性和结合律，并且有单位元，则称M为含幺半群(Monoid)、弱群或类群。,【例44】证明非空集合0,1是的一个群。已知运算法则是,（434）,（3）因为00

17、,1，且 则0,1集合中存在单位元e0； (4)因为集合0，1中的元素“0”和“1”，都有 则“0”和“1”都存在逆元素,“0”的逆元素就是“0”本身；“1”的逆元素就是“1”本身。由于在运算法则下，集合0,1满足群定义中的四个条件，按群的定义可得0，1集合是运算法则的一个群。,又因为0,1集合在运算法则下满足交换律，即 则由定义可知，集合0,1是运算法则的交换群。同理可证下列结论:(1)全体整数按照通常的加法可构成群，并且是Abel群、无限群。而在通常的乘法运算法，全体整数不构成群，因为除1外，其他元素都没有逆元，它只能构成含幺半群。同样，全体偶数在加法运算下构成群，而在乘法运算下不构成群。

18、全体实数在加法运算下构成群；而除0元素外的全体实数在乘法运算下构成群。,(2)Zn在模n的加法下构成群，群的阶为n。(3)Z*n在模n的乘法下构成群，群的阶为(n)。(4)所有n阶矩阵的全体M，在矩阵的加法运算下构成群，其单位元为0矩阵；在矩阵的乘法运算下，若为满秩矩阵则构成群；否则不构成群。,2.群的主要特性群的主要特征有以下两点。(1)一个群的单位元是惟一的，每一个群元素的逆元素也是惟一的。证明若e和e都是群G的单位元，则e和e必定又都是群G中的元素。当把e看做单位元，e看做另一元素时，有ee=e。当把e看做单位元；e看做另一元素时，又有ee=e，由群定义中的条件(3)有,(4-35),所

19、以e和e不可能是群G中两个不同元素。这就证明了单位元的惟一性。下面证明逆元的惟一性。若gG，且g具有逆元素：g1-1和g-12，根据群的定义，有,(436),(2)设G是运算法则的一个群，若g1G,g2G,则,(437),证明根据群的定义,有,(438),所以群G中任意两个元素g1和g2在指定运算法则下的运算值g1 g2的逆元素(g1 g2)-1等于逆元素g-12和g-11在运算法则下的运算值g-12g-11。,4.3.2子群及陪集1.基本概念设集合G是运算法则的一个群，H是群G的一个非空子集。如在运算法则下，集合H也构成一个群，则非空子集H称为群G的一个子群。记作 。显然，任何群G都有两个子

20、群：群G本身和仅仅由单位元构成的群。通常称这两个子群为平凡子群。除平凡子群之外的其他子群为真子群。例如：所有偶数在加法下构成的群是所有整数构成的加法群的子群。实际上，非空子集H在运算法则下只要满足以下两个独立条件，就符合子群定义的条件。,(1)具有封闭性。若h1H,h2H，且有,（439）,(2)子集H中存在一个单位元e。若hH，则必有eH，则有,(440),下面介绍为什么只要满足式(439)和式(440)两个独立条件，非空子集H就是群G在运算法则下的一个子群。(1)若h1H，h2H，h3G,因H是G的子集，所以必有h1G，h2G,h3G。由于G是运算法则的一个群，所以必有,(441),(2)

21、因为集合G是运算法则的一个群，所以G中必存在一个单位元e。集合H是群G的非空子集，由式(440)可知，H中又存在一个单位元e。根据群的单位元的惟一性，非空子集中的单位元e就是群G的单位元。这就是说，群G中的单位元e一定在其子群H之中，或子群H中的单位元e一定就是群G中的单位元e。,(3)若hH，因H是G的子集，所以必有hH。又因G是运算法则的一个群,则h在G中必有逆元素h-1，即有,(442),由式（440），有eH；由式(439)，即非空子集H的封闭性，必有h-1H。这就是说，非空子集H中任一元素h的逆元素h-1都在H之中，或者说，非空子集H中任一元素h在H中都存在逆元素h-1 。,所以运算

22、法则的群G的非空子集H只要满足在运算法则下的式(439)和式(440)两个独立条件，就能满足运算法则的群的四个条件和群G的子群的条件。下面介绍陪集的概念。设集合H=e,h2,h3,h2k是群G=g1,g2,g3,g2n的子群，gi是群G中的一个元素，但gi不是子群H中的元素，即gi G, gi，把,称为子群H在群G中的一个“左陪集”，把,称为子群H在群G中的一个“右陪集”。“左陪集”和“右陪集”中的第一个元素,称为“陪集首”。若群G是运算法则的交换群，那么“左陪集”和“右陪集”一定相同。即,(446),(444),(445),(443),这时，“左陪集”和“右陪集”通称为“陪集”。,2.子群的

23、主要性质子群有以下三个主要性质。(1)运算法则群G中所有元素均可由其子群H中的元素表示。这个特性说明，群G=g1,g2,g3,g2n的所有元素gi(i=1,2,2n)可由子群H=e,h2,h3,h2k的所有元素hi(i=1,2,2k;h1=e)及子群H的若干个陪集（或“左陪集”或“右陪集”）表示。,(2)群G中的两个元素g1和g2在子群H的同一陪集之中的充要条件是,(447),证明必要性。设群G中两个元素g1和g2在子群H的同一陪集之中。令该陪集的陪集首为gi，则,(448),由式（437）,得,充分性。设g1和g2是群G中的两个元素，且有,(450),则有,(451),(452),(453)

24、,令g1所在陪集的陪集首为gi，且在子群H中的元素hj的同一列，即令,(454),由式（453），得,(qj,k),(455),所以g1和g2所在陪集的陪集首都是gi，这就证明g1和g2在同一陪集中。,(3)设H是群G的子群，H的两个不相同的陪集，一定不相交。证明设两个不同陪集分别为giH和gjH(ij)。若这两个陪集相交,则有,(456),又设公共元素g处在hk(hkH)同一列；又处在hq(hqH)(qk)同一列，即设,(457),由式(457)有,(458),即有,(459),根据子群特性,由式(459)有,(460),由式(460)有,(461),(462),根据子群特性式(447)可得

25、，gi和gj在子群H的同一陪集之中。由假设可知， gi和gj又是两个陪集首，则由式(462)可知，由gi和gj产生的陪集一定是同一陪集,(463),这就是说，具有公共元素的两个陪集giH和gjH不可能是两个不同陪集，一定是同一陪集。这从反面证明，具有公共元素的两个陪集一定是同一陪集；两个不同陪集一定没有公共元素，即一定不相交。,4.3.3置换群及循环群1置换设是集合A到其自身的一一映射，则称为A的一个置换。例如,集合A=1,2,3。设2的映射为12,23,31,简记为,现在，在集合A上，再定义两个置换为:,其中:1为恒等置换。,那么可以定义置换的运算“”。例如(先进行2变换，再3变换)：,所以

26、说2和3互为逆元。以三个置换为元素构成的集合S=1,2,3构成了一个三阶有限群。,2置换群和n次对称群由置换元素i为集合元素的有限群称为置换群。由n个元素组成的有限集合A=1,2,n到自身的所有置换有n!个，这n!个置换组成的集合S=1,2,n!在置换运算下是一个n！阶有限群，称其为n次对称群。由以上定义可知,n次对称群一定是置换群，而n次对称群的子群也是一个置换群。已知群G,G，令H=k|kZ。因H为构成G的一个子群，所以称之为由生成的循环子群，记作,则称为它的生成元。若G=，则称G是一个循环群。在群G中，若bG且bn=e,e为单位元，则最小的n称为b的周期或元素b的阶。循环群的阶若为n，那

27、么生成元的周期为n。,由于在循环群中有m=(-1)-m，所以-1也是该群的一个生成元。那么对于群，有如下定理。定理47已知一个m阶群G，则G中的元素周期必为m的因子，从而有bG,bm=e。证明因G有限，故G中的任何元素b的周期不可能是。设b的周期为n，于是有循环群b的阶为n。由Lagrange定理知道n|m，故有bm=e。证毕,4.3.4域、环及有限域群是有一个二元运算的系统，环上有两个二元运算。域也定义了两个二元运算，由于在域中对加减乘除运算都封闭，因而许多与四则运算有关的问题都涉及到域的性质。1基本概念一个域F就是一些元素的集合，它具有的+(加法)和（乘法）运算满足下列性质。(1)F在“+

28、”和“”下是封闭的；(2)交换律：a+b=b+a,ab=ba;(3)结合律：(a+b)+c=a+(b+c),a(bc)=(ab)c；(4)分配律：a(b+c)=ab+ac,(b+c)a=ba+ca。进一步，F中必须存在元素0和1，满足：,(5)a+0=a；(6)a1=a；(7)对F中任意a，存在加法逆元(-a)，使a+(-a)=0;(8)对F中任意a0，存在乘法逆元(a-1)，使aa-1=1。以上性质对含有有限个和无限个元素的域都成立。 例如有理数全体、实数全体、复数全体对加法乘法分别构成域，分别称为有理数域、实数域和复数域。它们的元数是无穷的，故称其为无限域。域的集合元数是有限的，则称其为有

29、限域，一般用GF(p)或Fp表示，p表示其元数(阶)。有限域也称为Galois域或伽罗华域（GaloisField）。,例如0和1两个元素按模2加和模2乘构成域。该域仅有两个元素，记为GF(2)。若只满足域定义中的前7条性质，则称为环(ring)。注意：环的乘法没有单位元，当然更没有逆元,它其实是一个乘法的半群。若环中有乘法单位元，则称其为有单位元环。若环的乘法满足交换律，即对于任意a,bR，都有ab=ba,则称其为交换环或可换环。例如在普通加法乘法下：全体整数Z构成环；全体偶数构成环。Zn在模n的加法和乘法下构成环，称为剩余类环。实系数多项式全体在多项式加法和乘法下构成环。,另外，设Zx=a

30、0+a1x+a2x2+anxn|aiZ,n0的整数是整数环上的全体多项式集合，Zx对多项式加法乘法构成环，一般称其为整数环上的多项式环。,2.有限域GF(p) 中的计算有限域GF(p)定义为整数0,1,2,p-1的集合,相应的运算为模p的代数运算。如果a,bGF(p),则加法,a+br(modp ),(464),如果a,bGF(p),则乘法,abs(mod p),(465),令GF*(p)表示GF(p)中所有非零元素的集合，可证明在GF(p)中至少存在一个元素g，使得GF(p)中任意非零元素可以表示成g的某次幂的形式，这样的元素g称为GF(p)的生成元(或本原元)，a=giGF*(p)的乘法逆

31、元是a-1=g-i=g(-i)mod(p-1)。即,(466),【例45】已知有限域GF(23)=0,1,2，22，5是GF(23)的生成元，那么5的各次幂分别如表41所示。,表41GF(23) 的生成元5的各次幂,4.3.5子环及理想1.子环类似于子群，在环中也可定义子环。若环中的子集S关于环R中的代数运算也构成环,则称S为R的子环,或R是S的扩环。非空子集S是R的子环的充要条件是：(1)对任何两个元素a,bS，恒有a-bS；(2)对任何a,bS，恒有abS。 例如全体整数集合可构成一个可换环，以某一整数m的倍数全体构成其中的一个子集，该子集就是整数环中的一个子环。如m3，则所有3的倍数的全

32、体集合(0，3，6，9，)构成一个子环。一个环至少有两个子环，一个是由0元素组成，一个是环R本身，则称这两个子环为环R的假子环，其余的称为真子环。,2.理想理想是很重要的一类子环，它在环中的作用相当于正规子群在群中的作用。设R是交换环，S是R的非空子集，若(1)对任意两个元素a,bS，恒有a-bS；(2)对任意aS，rR，恒有ar=raS，则称S是R中的一个理想。,由此定义可知，理想其实就是可换环中的一个子环，该子环也称双边子环。由(1)可知S是一个阿贝尔加群，由(2)可知S的某些元素都由某一元素a的倍数组成。因此，若理想中包含了元素a，则它就包含了a的一切倍元。由于S构成了一个可换加群，所以

33、可用它作为一个正规子群，把R中的元素进行分类划分陪集。例全体整数Z构成一个可换环，某一整数m的倍数构成一个理想Sm，以此理想可把全体整数Z划分陪集。,3主理想由理想的条件(2)可知，理想中的一切元素都是某些元素的倍数组成。如果理想中的元素由一个元素的所有倍数及其线性组合生成，则称这个理想为主理想。在可换环R中，由一个元素aR所生成的理想S(a)=ra+na|rR,nZ，称为环R的一个主理想，称元素a为该主理想的生成元。以某一整数m的倍数所构成的理想Sm就是一个主理想，m是生成元。如果R是一个有单位元素的无零因子可换环，且R中的每一理想都是主理想，则称该R为主理想环。例如，整数环Z就是一个主理想

34、环。,4.环的零因子用(A，+，)表示一个环，那么加法群用(A，+)表示。约定环中的一些称谓如下：(1)加法群中的单位元用0表示，称为零元；(2)a的逆元写为-a，称为负元。而单位元指乘法半群中的单位元，逆元指乘法半群中的逆元。设环R，a、bR，若ab=0且a0和b0，则称a为左零因子，称b为右零因子。如果一个元素既是左零因子又是右零因子，则称其为零因子。,定理48环中无任何零因子的充要条件是乘法消去律成立，即 证明必要性。设a0，ab=ac有a（bc）=0，因为a0且没有零因子，故必须满足bc=0即b=c。类似的证明右消去律。充分性。设ab=0，若a0，那么对ab=a0进行消去律运算，则有b

35、=0。所以不存在a0，b0使ab=0，即环中无任何零因子。证毕,a0，ab=ac b=ca0，ba=ca b=c,(467),环中有无零因子体现了环内的一种运算上的性质，即消去律是否可以进行。这对方程的求解问题影响很大。设环(A，+，)，若A0是交换环，且无零因子，则称A为整环(Domain)。若A满足：(1)A至少有两个元素0和1；(2)A除去0元素之后，构成乘法群，则称A是一个除环(DivisionRing)。简单地说，一个可换的除环就是域。所以域是可换的，有单位元1，非零元有逆元的环，且域中一定无零因子。,定理49n是域的充要条件是：n为素数。证明必要性。假设n不是素数，有n=pq，p1

36、，q1;因为n=pq，即在n中有元素p,q，使pq=0且p0,q0。这表明p和q是零因子，与n是域矛盾。充分性。假设n=p为素数，则Zn0，对任意kZ*p，因gcd(k，p)=1，则存在a,bZ使ak+bp=1，即ak=1,所以k-1=a，即对任意kZ*p；k有逆元，故Z*p是群，因而Zn是域。证毕,4.4多项式环、域及群4.4.1基本概念1.有限域GF(p) 上的多项式系数属于某数域的多项式称为该数域上的多项式。比如，二进制系数的多项式称为二元域GF(2)上的多项式，p进制系数的多项式称为p元域GF(p)上的多项式。域的多项式的一般形式为,(468),则f（x）称为n次多项式,n为多项式f(

37、x)的阶（degree）,记为deg(f(x)。用Fpx表示系数取自域GF(p)的一切多项式的集合。Fpx中的多项式可以按通常的方式进行加法、减法和乘法运算。,2.剩余多项式的除法算法是指对Fpx中的任意一对多项式a(x)和b(x)0，存在惟一的一对多项式q(x)和r(x)，分别称为商和余数，满足a(x)=q(x)b(x)+r(x)，其中degr(x)degb(x)。该余数有时又称为剩余，并记作,(469),设a(x)、b(x)和f(x)都为GF(p)上的多项式，则剩余的两个重要性质为：(1)Rf(x)a(x)+b(x)=Rf(x)a(x)+Rf(x)b(x)；(2)Rf(x) (x)b(x)

38、=Rf(x)Rf(x)a(x)R f(x)b(x)。,3.同余令f(x)为Fpx中的一个固定多项式,且Fpx中的两个多项式g(x)和h(x),如果g(x)-h(x)能被f(x)整除,则g(x)和h(x)关于模f(x)同余,记作,(470),如果设g(x)=x9+x2+1,h(x)=x5+x2+1为定义在GF(2)上的多项式。因为,故,4.既约多项式设f(x)是次数大于0的多项式，若除了常数、常数与本身的乘积以外，不能再被域GF(p)上的其他多项式除尽，则称f(x)为域GF(p)上的既约多项式。次数至少为1的首一既约多项式为素多项式。所以，一个常数总是多项式的因子，f(x)是否既约与讨论的域有很

39、大关系。,5本原多项式对于有限域GF(p)上的m次既约多项式p(x)，若能被它整除的最简单首一多项式(xn-1)的次数npm-1，则称该多项式为本原多项式（PrimaryPolynomials）。本原多项式一定既约；但是既约多项式未必是本原的。,6多项式循环群由多项式的各次幂所构成的群称为多项式循环群（CycleGroup）。多项式是群元素之一，称为该循环群的生成元。比如，1,2,3,4,5,6,7,8,构成乘运算下的无限循环群；若7=1，必然产生以1,2,3,4,5,6为主值的周期性由7个元素组成(7阶)的有限循环群。,4.4.2多项式剩余类环以数为元素可以构成群、环、域，以多项式为元素同样

40、可以构成群、环、域。下面将讨论用多项式构成群、环、域的方法、条件和性质。某数域上多项式的集合在乘、加运算下可以构成一个多项式环，它是一个以多项式为环元素的交换环。,多项式的两个要素是系数和幂次，只要其中一个有无限取值，比如系数所在数域是无限域(实数、整数等)或多项式的幂次无限，则多项式环元素的数目也就无限，称之为无限环。然而在纠错码的实际使用中，码集总是有限的，对应的多项式环也应是有限环，因此必须在系数和幂次两个方面对构成环的多项式进行限制。最常用的方法就是利用模运算产生数量有限的剩余类。,GF(p)上的多项式在模p加、模f(x)乘运算下，多项式剩余类的全体所构成的交换环称为多项式剩余类环，记

41、作Rp(x)f(x)。显然，多项式剩余类环是靠GF(p)域保证系数有限，靠模f(x)乘保证幂次有限的。多项式运算中包含了系数间模p乘、加的数域运算。多项式剩余类环的环元素是模f(x)乘的产物，即A(x)B(x)除以f(x)的余式。余式也就是“剩余”类环名称的来历。,如果f(x)的最高次幂是n，多项式剩余类环Rp(x)f(x)中所有环元素的次数不高于n-1次，其通式形式为,（471）,如果多项式最高次项的系数为1，则称该多项式是首一多项式。仅包含最高次项和常数项1，且形式为xn+1的首一多项式称为n次最简首一多项式。,【例46】剩余类环Rp(x)f(x)中，p=2，f(x)=x3+x+1。若A(

42、x)=x2+x+1，B(x)=x2+1是两个环元素，求A(x)B(x)是什么元素?该剩余类环至多由多少个元素组成?它们分别是什么?解本题的多项式系数取自GF(2)=0,1，系数做模2加、模2乘。做一般的多项式乘法运算,然后将结果除以f(x)后取余，得：,4.4.3多项式域 定理410若f(x)是GF(p)上的n次多项式，Fpx/f(x)是GF(p)域上次数小于n的多项式的全体，则次数小于n的多项式全体Fpx/f(x)构成环，当且仅当f(x)是Fpx/f(x) 上的既约多项式时，此环是域。 证明为了证明一个环是域，必须证明该环上的每一个非零元素都有的一个乘法逆元。,设s(x)是该环上的非零元素。

43、因为s(x)包含在Fpx/f(x)中，则有degs(x)degf(x)。设a(x)和b(x)都是GF(p)上的多项式,可以证明两个多项f(x)和s(x)的最大公因子可表示为,（472）,充分性。因为f(x)在Fpx上是既约的，所以有,（473）,于是,（剩余的性质（1）,(剩余的性质（2）,故Rf(x)b(x)是s(x)的乘法逆元。,必要性。假定f(x)的次数至少为2，而且不是素多项式（次数为1的多项式总是既约的)。因此存在次数至少为1的多项式r(x)和s(x)，使,（474）,若环Fpx/f(x)确实为域，那么r(x)和r-1(x)的乘法有意义，因为域中所有多项式都必存在对应的乘法逆元。因此

44、,(475),但已经假定s(x)0，因此矛盾,此矛盾表明该环不是域。所以多项式f(x)是既约。 证毕这样，就得到了一种产生伽罗瓦域的漂亮过程!若能找到GF(p)上次数为n的一个素多项式，就可以构造一个有pn个元素的伽罗瓦域。这样的域将含有的多项式作为其元素。这些多项式将由定义在GF(p)上的所有次数小于n的多项式构成。容易看到，共有pn个这样的多项式，它们组成了扩域GF(pn)上的元素。若f(x)是GF(p)上的n次既约多项式，Fpx/f(x)是GF(p)域上次数小于n的多项式的全体，则Fpx/f(x)在模p加、模f(x)乘运算下构成一个pn阶的有限域，称为GF(p)域的扩域(Extensio

45、nField)，写作GF(pn)。称GF(p)是扩域的基域。,【例48】求GF(24)和既约多项式f(x)=x4+x+1对应多项式域元素和GF(2)元素组合表示的域元素。解,【例49】用多项式基表示有限域GF(24),多项式f(x)=x4+x+1,计算(1)1011+1001=?(2)(1101)(1001)=?解可以验证f(x)是GF(24)上的不可约多项式，则GF(24)中的元素的计算为：1011+1001=0010,(1101)(1001) mod f(x),表42生成元a的各次幂,GF(p)和 GF(pn)一一对应只是一种映射或衍生，两者的含义毕竟不同，所以写法不同。例如，二元扩域绝不

46、能写成GF(4)，尽管在数值上22=4。扩域区别于多项式环的不同之处是强调了非零域元素逆元的存在。如果赋予扩域更多限定条件，它还可以具有更多特性。,4.4.5多项式群定理411若p(x)是GF(p)上的m次本原多项式，则GF(pm)域上次数小于m的非零多项式的全体(共pm -1个)，在模p(x)乘运算下构成一个多项式循环群。也就是说，扩域GF(pm)里至少存在一个本原元(代表一个次数小于m的多项式)，它的各次幂0,1,2,pm-2构成了扩域GF(pm)的全部非零域元素。,对照定理410、定理411及多项式剩余类环的定义,可知：以GF(p)上的多项式p(x)为模的乘运算可生成剩余类环，以既约多项

47、式f(x)为模的乘运算可生成多项式域，以本原多项式p(x)为模的乘运算所生成的非零域元素可以构成多项式循环群。可见模多项式的限制条件越多，环元素具备的性质也就越多。以上两条定理是存在性定理，下面的定理说明如何找到构成循环群的生成元。,定理412GF(p)上的本原多项式p(x)在扩域GF(pm)上的根一定是本原元。证明由本原多项式的定义知，p(x)能整除xn-1,即,式(481)可改写成：,(482),(481),设是本原多项式p(x)的根，即代入p(x)后满足p()=0，则将代入式(482)后可得,(483),所以 因为0=1,12pm-21，而pm-1 =0=1，的pm-1个幂次0pm-2不

48、但构成了全部pm-1个非零扩域元素，而且这些元素构成循环群，所以是本原元。 证毕 综上所述，可知构成循环群的步骤如下：先找一个GF(p)上的m次本原多项式p(x)；再取其根及根的各次幂0, pm-2 ，并构成循环群元素。,(484),定理413GF(pm)扩域上非零元素k(k=0,1,pm-2)的阶一定是pm-1的因子，其值为由式(485)算出的非零元素k的阶n，也就是该元素的循环周期，或者说是该元素的各次幂所能产生的域元素的个数。如果元素的阶n=pm-1，则说明它可以产生全部非零域元素，是本原元；如果元素的阶npm-1，则n一定是pm-1的因子，必能整除pm-1，该域元素是非本原元。下面给出

49、定理413的推论。,（485）,推论41循环群中，n阶元素的n次幂恒等于1。证明设n阶域元素k是本原元的k次幂且 ，则,（486）,式(486)中gcd(k,pm-1)是k的因子，即k/gcd(k,pm-1)是整数pm-1 =1。证毕,【例410】p(x)=x4+x+1是GF(2)上的本原多项式。试用本原元的各次幂生成二元扩域GF(24)的全部域元素，并计算各元素的阶。解令为本原多项式p(x)= x4+x+1的根，m=4，则p(x)|x=p()=4+1=0，即4=+1。因为为本原元，其阶为n=2m-1=24-1=15，由推论41可知15=1。的各次幂0,1,2, 2m-2=14可生成GF(24

50、)的全部非零域元素，且这些域元素构成一个循环群。将的各次幂列出，得表43中第一列的值，这是一个乘运算下的15阶循环群。,表43本原多项式p(x)=x4+x+1的根生成的循环群,利用关系式4=+1，可将的各次幂化作的低于4次的多项式(尽管本身就是多项式)。比如，8=44=(+1)(+1)=2+1=2+1与8次幂对应的多项式在表43的第二列。因为模既约多项式的剩余类构成域,则所有模p(x)剩余类列在表43的第三列。因为矢量与多项式存在一一对应的关系,如对于矢量(1101)表示的码元，可写成多项式x3+x2+1，其系数代表码元取值，x的幂次指示码元位置。利用此对应关系，可将多项式写成矢量形式列在表4