第2章 近世代数.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,天津大学电子信息工程学院,*,第,2,章 近世代数简介,线性分组码中最重要的一个子类,-,循环码,(RS,、,BCH,码,),，它的结构完全建立在,有限域,的基础之上，被称为,代数几何码。,有限域是以近世代数,为基础。,1/29/2026,1,天津大学电子信息工程学院,2.1,几个概念,1.,质数（素数）,一个大于,1,的正整数,，,只能被,1,和它本身整除,。,2.,合数,一个,大于,1,的正整数,，,除了能被,1,和本身整除以外,，,还能被其他的正整数整除,。,例,2-1,2,，,3,，,5,，,7,，,9,，,11,，,13,，,17,，,19,都是质数；,4,，,6,，,8,，,9,，,10,，,都是合数；,这样，全体正整数又分为：全体素数和全体合数。,1/29/2026,2,天津大学电子信息工程学院,3.,群,(Group),设,G,是非空集合,(set),，并在,G,内定义了一种代数运算,(operation),“,。,”,，若满足下述公理：,（,1,）,具有封闭性,(is closed),；,（,2,）,结合率 成立,(is,associative,),；,（,3,）,G,中有一个恒等元,e,存在,(exist an identity element),；,（,4,）,有逆元 存在,(contain an inverse element),。,称,G,构成一个群,。,1/29/2026,3,天津大学电子信息工程学院,（,1,）加群,(,addition group,),、乘群,(,multiplication group,),（针对群中的运算）,（,2,）群的阶,（针对群中元素的个数）,（,3,）有限群,(,finite group,),、无限群,(,infinite group,),（针对群中元素的个数）,（,4,）交换群,(,commutative group,),或阿贝尔群,(,Abel group,),（针对群中的运算）,1/29/2026,4,天津大学电子信息工程学院,例,2-2,G1,：,整数全体。,对加法构成群,，无限加群；,对乘法不够成群,。,Why?,G2,：,实数全体。,对加法构成群；,除,0,元素之外,的全体实数，对乘法构成群。,单位元,e=1,。,这两个群都是无限群。,G1,和,G2,有都是,阿贝尔群,。,群,将,和,联系在一起？,1/29/2026,5,天津大学电子信息工程学院,4.,域,(Field),对于非空元素集合,F,，,若在,F,中定义了,加法,(,addition,),和,乘法,(,multiplication,),两种运算，且满足下面的公理：,（,1,）,F,关于加法构成,阿贝尔群,，其,加法恒等元,记为,0,；,（,2,）,F,中,非,0,元素全体,对乘法构成阿贝尔群，其,乘法恒等元（单位元）,记为,1,。,（,3,）加法和乘法之间满足如下分配率,(,distributive,),：,则,称,F,是一个域,。,1/29/2026,6,天津大学电子信息工程学院,（,1,）,域的阶,（,针对群中元素的个数），,记为,q,。,（,2,）,有限域或,伽逻华,（,Galois,）域，表示为：,GF(q,),。,域,将,和,联系在一起？,1/29/2026,7,天津大学电子信息工程学院,例,2-3,F1,：,有理数全体,、,实数全体,对加法和乘法都分别构成域，分别称为有理数域和实数域。,F2,：,0,、,1,两个元素,模,2,加,构成域；由于该域中只有两个元素，记为,GF(2),。,1/29/2026,8,天津大学电子信息工程学院,定理：,设,p,为质数,，则,整数全体,关于,p,模,的剩余类：,0,，,1,，,2,，,，,p-1,，,在模,p,的运算下（,p,模相加和相乘），构成,p,阶有限域,GF(p),。,例,2-4,验证以,p=3,为模的剩余类全体：,0,，,1,，,2,构成一个有限域,GF(3),。,+,0,1,2,0,0,1,2,1,1,2,0,2,2,0,1,0,1,2,0,0,0,0,1,0,1,2,2,0,2,1,1/29/2026,9,天津大学电子信息工程学院,分析：是否构成域？,对,加法,是否构成群？除,0,之外对,乘法,是否构成群？,（,1,）对两种运算,满足封闭性,，即有,a,。,b G,；,（,2,）,满足结合率,，即有,(a,。,b),。,c=a,。（,b,。,c,）；,（,3,）,有恒等元,（加法为,0,，乘法为,1,）；,（,4,）,有逆元,。即对任意,a,G,，,存在有,a,的逆元,a,-1,G,，,使,a,。,a,-1,=a,-1,。,a=e,。,1/29/2026,10,天津大学电子信息工程学院,B.,是否为阿贝尔群？,是否可交换：,a,。,b=b,。,a,（,满足乘法、加法交换率）,C.,是否满足分配率？,1/29/2026,11,天津大学电子信息工程学院,5.,循环群,如果,一个元素,的各次,幂,0,，,1,，,2,，,的全体构成了一个群，称为,循环群,（,cycle,group,），,元素称为,生成元,或者,本原元,（,primitive element,）,。,记作：,G=,0,，,1,，,2,，,，,其中,0,=e,是单位元,。,可以证明，有限域,GF(q),的,q-1,个非,0,元素,，在,模,q,乘运算下,，可以构成一个,循环群,（幂群,），即,G,上的所有非,0,元素可以由一个元素,的各,次幂,0,，,1,，,2,，,q-1,生成,。,1/29/2026,12,天津大学电子信息工程学院,例,2-5,q=5,的伽逻华域,GF(5)=0,1,2,3,4,，由,5,个域元素组成，其中非零元素为,1,2,3,4,，进行,模,5,乘运算,。,为了弄清那些元素是,本原元,，分别,计算各元素的各次幂,。,由本原元可以产生所有的域元素。,1/29/2026,13,天津大学电子信息工程学院,GF(5),中非,零元素的幂,、,阶及其逆元,元素,各 次 幂,元素的阶,加法逆元,乘法逆元,0,1,2,3,1,1,1,1,1,1,4,1,2,1,2,4,3,（,8,）,4,3,3,3,1,3,4,（,9,）,2,（,27,）,4,2,2,4,1,4,1,（,16,）,4,（,64,）,2,1,4,（,1,）,元素的阶,（能产生域元素的个数）,：,（,2,）域元素,2,和,3,的各次幂,可以生成全部非零域元素,，所以,2,和,3,都是本原元。,（,3,）元素,1,的各次幂只能生成元素,1,（阶为,1,），,4,只能生成元素,1,和,4,（阶为,2,），故都不是本原元（生成元）。,1/29/2026,14,天津大学电子信息工程学院,6.,环（,Ring,）,定义：在非空集合,R,中，若定义了两种代数运算加和乘，且满足：,（,1,）集合,R,在加法运算下构成阿贝尔群；,（,2,）乘法有封闭性，对于任何,a,b,R,，有,ab,R,；,（,3,）,乘法结合率成立，且加法和乘法之间分配率成立，即对任何,a,b,R,，有,a(b+c)=,ab+ac,(b+c)a=,ba+ca,则,称,R,是一个环,。,1/29/2026,15,天津大学电子信息工程学院,环,将,和,联系在一起？,What is the relationship with Group,Field and Ring?,What is the difference between Field and Ring?,1/29/2026,16,天津大学电子信息工程学院,7.,同余和剩余类,定义：若两个整数,a,、,b,能,被同一整数,m,整除,，,余数相同,，即,则称,a,、,b,关于模,m,同余,，记为,由同余的概念，可以将全体整数加以分类，,把余数相同的归成一类,，即由,共有,m,个剩余类。,一般地讲，若模数为,m,，,则全体整数可以按照模,m,划分成,m,类，,0,，,1,，,，,m-1,，,或用,0,，,1,，,2,，,m-1,表示，称这样的一组数为,模,m,的剩余类,。,1/29/2026,17,天津大学电子信息工程学院,例,2-6,如果取,m=7,，,则对全体整数，可如下划分：,剩余类的加法和乘法运算,1/29/2026,18,天津大学电子信息工程学院,2.2,多项式剩余类环和域,1.,域上多项式的定义,多项式与码字的,关系,：桥梁,；,多项式的,系数,表示,；,x,的,幂次,表示,；,域上的多项式,针对系数定义,；,例如,二进制系数多项式,，称为,二元域,GF(2),上的多项式。,q,进制系数的多项式，称为,q,元域,GF(q),上的多项式。,群、环、域,对多项式也成立,。,1/29/2026,19,天津大学电子信息工程学院,域上多项式：,GF(q,),上,多项式的定义：,1/29/2026,20,天津大学电子信息工程学院,(1),多项式的两要素,(2),多项式次数,(3),首一多项式,(4),最简首一多项式,(5),多项式的有限性分析,1/29/2026,21,天津大学电子信息工程学院,2.,多项式剩余类环存在定理,若以有限,域,GF(q,),上,多项式,为模做乘法运算，,q,为模做加运算,，得到的,多项式剩余类,的全体，可以构成一个交换环，称为,多项式剩余类环，记为,Rq(x),f,(,x,),。,多项式剩余类环的,有限性,可以得到保证。,系数有限性,幂次的有限性,1/29/2026,22,天津大学电子信息工程学院,系数模,q,加和,模,f(x),乘运算,：,A(x,),、,B(x,),是两个环元素，,模,q,加,模,f,(,x,),乘,1/29/2026,23,天津大学电子信息工程学院,多项式,f,(x),的,最高次幂为,m,，有限域为,GF(q,),。,多项式剩余环类,Rq(x),f,(,x,),中,环元素,的,最高次数,为,；,多项式的,一,般形式,为：,这个环,中共有,个元素？,1/29/2026,24,天津大学电子信息工程学院,例,2-7,剩余类环为,Rq(x),f,(,x,),，,q=2,，,f,(x)=x,3,+x+1,。,若,A(x,)=x,2,+x+1,，,B(x)=x,2,+1,是两个,多项式,。,求,A(x)B(x),构成的剩余类环最多,有多少个元素,？,解：,（,1,）一般多项式乘法运算,1/29/2026,25,天津大学电子信息工程学院,（,2,）用,f,(x),除上面的多项式，有,1/29/2026,26,天津大学电子信息工程学院,得到,，,A(x)B(x),modf(x,),=,x,2,+,x,。,由于,f(x),是,3,次多项式，因此该剩余类环的,最高次幂,不会超过,2,，一般形式由下式给出：,由于环元素只有,3,个系数,，最多的,不同组合有,8,种,，因此该剩余类环最多,只有,8,个环元素,（包括多项式和常数）,。,1/29/2026,27,天津大学电子信息工程学院,2.3,多项式域和循环群,1.,既约多项式（,Irreducible,polynomials,）,定义,：,设,P,l,(,x,),是次数大于,0,的多项式。如果,除,常数,C,和,C,P,l,(,x,),之外,，不能被域,GF(q),上的其它多项式整除，则称,f,(,x,),是域,GF(q),上,的,既约多项式,。,1/29/2026,28,天津大学电子信息工程学院,(1),常数,总是多项式的因子,。,(2),一个多项式,f(x,),是否为既约多项式与所定义的,域,有关。,(3),一个多项式,既约的充要条件,：多项式,P,l,(x,),不能分解成两个次数低于,P,l,(x),的多项式的乘积。,(4),完全分解,：,n,次多项式最多能分解成,n,个,一次多项式,的乘积，被称为完全分解。,(5),一次多项式,一定是既约的。,1/29/2026,29,天津大学电子信息工程学院,2.,本原多项式（,Primary Polynomials,）,定义：,对于,有限域,GF(q),上的,m,次既约多项式,P(x),，,若能被它整除的,最简首一多项式,（,x,n,-1,）,的次数为：,则称这个多项式,P(x),为,本原多项式,。,本原多项式一定是既约的；,但既约多项式未必是本原的。,1/29/2026,30,天津大学电子信息工程学院,3.,多项式循环群（,Cycle Group,）,定义,：群内的,所有元素,由,多项式,的各次幂,构成，称为多项式循环群,。,多项式,是一个群元素，被称为,循环群的生成元,。,例,2-8,，,1,，,1,，,2,，,3,，,4,，,5,，,，,构成,无限循环群,；,若,7,=1,，以,1,，,1,，,2,，,3,，,4,，,5,，,6,为周期，则称,0,=1,，,1,，,2,，,3,，,4,，,5,，,6,为,7,阶,有限循环群,。,1/29/2026,31,天津大学电子信息工程学院,域存在定理,定理,2.1,若,f,(,x,),是有限域,GF(q),上的,m,次既约,多项式，则,GF(q),域上次数小于,m,的多项式的全体，,在模,q,加、模,f(x),乘,运算下构成一个,q,m,阶,有限域。,称,其为,是,GF(q,),的,扩展域,（,Extension Field,），,记为,GF(q,m,),。称,GF(q),是,GF(q,m,),的,基域,。,1/29/2026,32,天津大学电子信息工程学院,例,2-9,二元域,GF(2),上，模,2,加、模,x,2,+x+1(m=2),乘运算下构成一个,扩展域,：,GF(2,2,)=0,1,x,x+1,，,基域,：,GF(2)=0,1,1/29/2026,33,天津大学电子信息工程学院,基域,GF(q,),是,数域,，有,q,个,域元素；,扩展域,GF(q,m,),则是,多项式域,，有,q,m,个,域元素；,m,个,基域的元素对应扩展域的,一个,元素：,扩展域,GF(2,2,),的元素,0,1,x,x+1,m(2),个域,GF(2),的元素,00,01,10,11,1/29/2026,34,天津大学电子信息工程学院,循环群存在定理,定理,2.2,若,P(x),是,GF(q),上,m,次,本原多项式,，,则,GF(q,m,),域上,幂次小于,m,的非,0,多项式的全体,（共有,q,m,-1,个），在模,q,加、模,P(x),乘运算下形成一个,多项式循环群,。,在扩展域,GF(q,m,),里，至少存在一个本原元,，其各次幂,能构成扩展域,GF(q,m,),的,全部非,0,的域元素,。,1/29/2026,35,天津大学电子信息工程学院,总 结,GF(q,),上多项式,若为：,（,1,）,一般,多项式,f,(x),，构成,q,m,阶,。,（,2,）,既约,多项式,P,l,(x),，构成,q,m,阶,。,（,3,）,本原,多项式,P(x,),，构成,q,m,-1,阶,。,对多项式的限制越多，扩展域具备的性质也就越多。,如何找到构成循环群的生成元,？,1/29/2026,36,天津大学电子信息工程学院,2.4,循环群的生成元,定理,2.3,GF(q,),上的,m,次,本原多项式,P(x),的,根,，一定是扩展域,GF(q,m,),上的,本原元,。,证明：,1/29/2026,37,天津大学电子信息工程学院,构成循环群的步骤：,找到,GF(q),上的一个,m,次本原多项式；,取其根,，并计算的各次幂,得到扩展域的所有非,0,元素，即循环群。,1/29/2026,38,天津大学电子信息工程学院,2.5,域元素的性质,本原元,，,用表示，,各次幂可以生成,扩展域,GF(q,m,),中,全部,q,m,-1,个,非,0,域元素,；,非本原元,，,用表示，,只能生成,部分,域元素。,下面的定理回答：,什么样的域元素是本原？,什么样的域元素是非本原？,对于非本原的元素，它们的阶又是多少？,1/29/2026,39,天津大学电子信息工程学院,定理,2.4,扩展域,GF(q,m,),上,的非零元素,k,的,阶,一定是,q,m,-1,的因子，其值为：,GCD,表示,最大公约数,（,Greatest Common Divisor,）。,1/29/2026,40,天津大学电子信息工程学院,如果,n=,q,m,-1,，本原元；,如果,n,q,m,-1,，非本原元，,n,一定是,q,m,-1,的一个因子,，,一定能够整除,q,m,-1,。,推论,2-4,在循环群中，,n,阶域元素,的,n,次幂,恒等于,1,。,证明：,1/29/2026,41,天津大学电子信息工程学院,例,2-10,P(x,)=x,4,+x+1,是,GF(2),上的,本原多项式,，试用本原元的各次幂生成二元扩展域,GF(2,4,),的,全部域元素,，并计算域元素的阶。,解：,1/29/2026,42,天津大学电子信息工程学院,各次幂,k,的多项式,多项式的系数,m,重,元素的阶,15/GCD(k,15),0,1,（,0001,）,1,1,（,0010,）,15,2,2,（,0100,）,15,3,3,（,1000,）,5,4,+1,（,0011,）,15,5,2,+,（,0110,）,3,6,3,+,2,（,1100,）,5,7,3,+1,（,1011,）,15,用本原多项式,P(x)=x,4,+x+1,生成的循环群,1/29/2026,43,天津大学电子信息工程学院,各次幂,k,的多项式,多项式的系数,m,重,元素的阶,15/GCD(k,15),8,2,+1,（,0101,）,15,9,3,+,（,1010,）,5,10,2,+1,（,0111,）,3,11,3,+,2,+,（,1110,）,15,12,3,+,2,+1,（,1111,）,5,13,3,+,2,+1,（,1101,）,15,14,3,+1,（,1001,）,15,1/29/2026,44,天津大学电子信息工程学院,结论：,（,1,）本原元不是唯一的，共有,8,个本原元。,（,2,）不是所有的元素都是本原元。,（,3,）,以,7,为例，可以生成,15,个域元素。,1/29/2026,45,天津大学电子信息工程学院,2.6,域元素、根、最小多项式的关系,定理,2.5,扩展域,GF(q,m,),上的所有非零域元素,0,，,1,，,2,，,，,qm-2,都是,GF(q),上多项式,的根，即 可,完全分解,为,一次项的乘积。有，,证明：,1/29/2026,46,天津大学电子信息工程学院,定理,2.6,扩展域,GF(q,m,),上,域元素和,的,q,l,次幂等于元素,q,l,次,幂的和,，即有：,i,是,域元素。,1/29/2026,47,天津大学电子信息工程学院,定理,2.7,如果,是,GF(q,),上的,p,次,多项式,f,(,x,),的,根,，那么,的,q,l,(,l,i,=1,2,l,p,),次幂,也,一定,是,f,(,x,),的,根,。,即：如果,是,f,(,x,),的根,，,那么,也一定是,f,(,x,),的根,；,p,是多项式的次数，,l,是,小于,p,的数。,证明：,1/29/2026,48,天津大学电子信息工程学院,费尔马,(Fermat),定理,：,由定理,2-5,，,GF(q,m,),上的任意一个,域元素,一定是,所以有，,1/29/2026,49,天津大学电子信息工程学院,由定理,2-7,：,共轭元具有相同的基底 ,q,(,是,一个域元素，,q,是基域的阶,),，费马定理限制了共轭根系的个数,（共有,m,个）,。,1/29/2026,50,天津大学电子信息工程学院,根据费尔马定理，,共轭元可构成循环,：,一个多项式的根，可以来自多个不同的根系；,如果一个,多项式,的,所有根,来自同一个基底为,的根系，称这样的多项式为,的最小多项式,；,最小多项式,在,GF(q),中,一定是既约,的，,本原元,共轭根系对应的,最小多项式的次数等于,m,。,1/29/2026,51,天津大学电子信息工程学院,定理,2.8,：,GF(q),上的多项式 一定可以分解成若干个最小多项式之积，即有，,l,i,次最小多项式必然有,同一个根系的,l,i,个,共轭元作为根,(,这里,q=2),，,其中,l,i,不会超过,m,，,所以,i,(,x,)=,l,i,m,。,1/29/2026,52,天津大学电子信息工程学院,综合定理,2.5,，有,上式说明，在 的,q,m,个根中，所有,的根都来自不同的,k,个共轭根系。,下面的例子，说明了共轭元、最小多项式和多项式 之间的关系。,1/29/2026,53,天津大学电子信息工程学院,例,2-11,找出由本原多项式,P(,x,)=,x,4,+,x,+1,生成的二元扩展域,GF(2,4,),上,各非零元素,的共轭元，并计算与这些共轭元对应的,最小多项式,。,解：,1/29/2026,54,天津大学电子信息工程学院,各次幂,k,的多项式,多项式的系数,m,重,元素的阶,15/GCD(k,15),0,1,（,0001,）,1,1,（,0010,）,15,2,2,（,0100,）,15,3,3,（,1000,）,5,4,+1,（,0011,）,15,5,2,+,（,0110,）,3,6,3,+,2,（,1100,）,5,7,3,+1,（,1011,）,15,用本原多项式,P(x)=x,4,+x+1,生成的循环群,1/29/2026,55,天津大学电子信息工程学院,各次幂,k,的多项式,多项式的系数,m,重,元素的阶,15/GCD(k,15),8,2,+1,（,0101,）,15,9,3,+,（,1010,）,5,10,2,+1,（,0111,）,3,11,3,+,2,+,（,1110,）,15,12,3,+,2,+1,（,1111,）,5,13,3,+,2,+1,（,1101,）,15,14,3,+1,（,1001,）,15,1/29/2026,56,天津大学电子信息工程学院,共轭元及对应的最小多项式,共轭元,最小多项式,元素阶,0,1,(x)=x+1,1,1,2,4,8,2,(x),=x,4,+x+1,15,3,6,9,12,3,(x),=x,4,+x,3,+x,2,+x+1,5,5,10,4,(x),=x,2,+x+1,3,7,11,13,14,5,(x),=x,4,+x,3,+1,15,1/29/2026,57,天津大学电子信息工程学院,根据定理,2-8,1/29/2026,58,天津大学电子信息工程学院,