密码学基础群-(循环群-生成元).ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1,群的概念,定义,设,G,是一个非空集合,“,”,是,G,是上的一个代数运算,即,对所有的,a,b,G,有,a,b,G,.,如果,G,的运算还满足,:,(G1),结合律,:,即对所有的,a,b,c,G,有,(,a,b,),c,=,a,(,b,c,)(G2),G,中存在元素,e,使得对每个,a,G,有,e,a,=,a,e,=,a,(G3),对,G,中每个元素,a,存在元素,b,G,使得,a,b,=,b,a,=,e,.,则称,G,关于运算,“,”,构成一个群,(group),记为,(,G,).,2,注,1:(G2),中的元素,e,称为群,G,的单位元,(unit element),或恒等元,(identity).,群,G,的单位元是唯一的,.,注,2:(G3),中的元素,b,称为元素,a,的逆元,(inverse).,元素,a,的逆元是唯一的,记为,a,-,1,.,即有,a,a,-,1,=,a,-,1,a,=,e,3,有限群,交换群,如果群,G,的运算还满足,:,(G4),交换律,:,即对所有的,a,b,G,有,a,b,=,b,a,.,则称,G,是一个交换群,(commutative group),或阿贝尔群,(abelian group).,G,中元素的个数称为群,G,的阶,(order),记为,|,G,|.,如果,|,G,|,是有限数,则称,G,是有限群,(finite group),否则称,G,是无限群,(infinite group).,例,:,整数加群,(,Z,+);,有理数加群,(,Q,+);,实数加群,(,R,+);,复数加群,(,C,+).,令,Q,*=,Q,-0,(,Q,*,),是群,;,Q,+,=,q,Q,|,q,0,(,Q,+,),是群,.,4,群的概念,例,1,设,G,=1,-1,i,-i,则,(,G,),是一个有限交换群,.,元素,a,1,-1,i,-i,逆元,a,-1,1,-1,-i,i,5,例,2,设,m,Z,+,Zm,=0,1,m,-1,则,(,Z,m,),是一个有限交换群,.,称为模,m,剩余类加群,.,单位元是,e,=0;,a,Z,m,的逆元,a,-,1,=,m,-,a,.,特别地,:,取,m,=5,有,Z,5,=0,1,2,3,4,元素,a,0,1,2,3,4,逆元,a,-1,0,4,3,2,1,6,有时把交换群,(,G,),记为,(,G,+),称为,“,加群,”,.,把运算,“,”,称为,“,加,”,法,运算结果记为,:,a,b,=,a,+,b,称为,a,与,b,的,“,和,”,;,单位元称为,“,零元,”,记为,“,0”;,a,G,的逆元称为,G,的负元,记为,:“-,a,”,即有,a,+(-,a,)=0.,7,例,1,G,=1,-1,i,-i,(,G,*,),是一个有限交换群,.,可记为,:(,G,*,)=(,G,+),运算式为,:,1+(-1)=-1,1+i=i,1+(-i)=-i,(-1)+i=-i,(-1)+(-i)=i,i+(-i)=1,1+1=1,请问零元是？利用,a+e,e,+,a=a,试求,(-i)+(-i),i+i,(-1)+(-1).,8,例,2,加群,:(,Z,5,)=(,Z,5,+),其中,Z,5,=0,1,2,3,4.,零元,0=0,负元为,:,元素,x,0,1,2,3,4,负元,-,x,0,4,3,2,1,9,群的概念,有时把群,(G,),记为,(G,),称为“乘群”,.,把运算“”称为“乘”法,运算结果记为,:ab=ab,称为,a,与,b,的“积”,;,运算符号通常省略,简记为,:ab=ab=ab.,单位元记为,:e=1.,10,例,3,设,mZ,+,Z,m,=0,1,m-1,则,(Z,m,),不是一个群,.,元素,0,无逆元,!,0?=1,找不到这样的元素！,例,4,设,mZ,+,是素数,Z,m,*=1,2,m-1,则,(Z,m,*,),是一个有限交换群,.,单位元,:e=1;aZ,m,的逆元,a,-1,:aa,-1,=1(mod m).,11,特别地,:,取,m=5,有,Z,5,*=1,2,3,4,11,1 mod 5,所以,1,的逆元素是,1,求出其他元素的逆元素,12,元素,a,1,2,3,4,逆元,a,-1,1,3,2,4,元素,a,的逆元,13,群的幂,设,(,G,),是一个群,n,Z,+,a,G,的,n,次幂为,:,a,n,=,a,a,a,(,n,个,a,),a,0,=,e,a,-,n,=(,a,-1,),n,.,指数法则,:,设,a,b,G,n,m,Z,则有,(1),a,n,a,m,=,a,n+m,;,(2)(,a,n,),m,=,a,nm,;,(3),如果,G,是一个交换群,则,(,a,b,),n,=,a,n,b,n,.,14,加群的倍数,设,(,G,+),是一个加群,n,Z,+,a,G,的,n,倍为,:,na,=,a,+,a,+,+a,(,n,个,a,),0,a,=0,(-,n,),a,=,n,(-,a,).,倍数法则,:,设,a,b,G,n,m,Z,则有,(1),na,+,ma,=(,n,+,m,),a,;,(2),m,(,na,)=(,nm,),a,;,(3),n,(,a,+,b,)=,na,+,nb,.,15,群元素的阶,设,G,是一个群,e,是,G,的单位元,a,G,如果存在正整数,r,使得,a,r,=,e,则称,a,是有限阶的,否则称,a,是无限阶的,.,如果,a,是有限阶的,则把满足,a,r,=,e,的最小正整数,r,称为,a,的阶,(order),记为,ord,a,=,r,.,如果,a,是无限阶的,则记,ord,a,=,.,16,计算群,(,Z,5,*,),每个元素的阶,Z,5,*,=1,2,3,4.,解：对于,a,=2,有,2,1,=2,2,2,=2,2=4,2,3,=2,2,2=8=3,2,4,=2,2,2,2=16=1.,ord 2=4.,下面，请求出各元素的阶,17,a,1,2,3,4,a,的阶,1,4,4,2,元素,a,的阶如下,18,例,7,计算群,(,Z,6,),每个元素的阶,Z,6,=0,1,2,3,4,5.,解,:,对于,a,=2,有,1,2=2,2,2=2,2=4,3,2=2,2,2=6=0.,ord 2=3.,a,0,1,2,3,4,5,Ord,a,1,6,3,2,3,6,19,设,G,是一个群,如果存在,a,G,使得,G,=,a,1,a,2,=,则称,G,是一个循环群,(cyclic group),并称,a,是的一个生成元,(generator).,如果,G,是一个,n,阶循环群,则,G,=,a,1,a,2,a,n,=.,提示,:,计算时请从,a,1,开始,20,如果,G,是一个,n,阶循环群,且元素,a,G,的阶,=,群,G,的阶,则,a,是,G,的一个生成元,.,例,8,设,m,Z,+,Z,m,=0,1,m,-1,则,(,Z,m,),是,m,阶循环群,.1,是一个生成元,.,21,特别地,:,取,m,=6,Z,6,=0,1,2,3,4,5,的生成元有,:1,5.,1,5=5,2,5=10=4,3,5=15=3,4,5=20=2,5,5=25=1,6,5=30=0.,Z,6,=0,1,2,3,4,5=6,5,5,5,4,5,3,5,2,5,1,5.,注意,:,循环群的生成元不是唯一的,!,22,循环群,定理 设,p,是素数,则,(,Z,p,*,),是,p,-1,阶循环群,.,Z,p,*,的生成元,a,称为,Z,的一个模,p,元根,(primitive root).,23,群,(,Z,5,*,),是,4,阶循环群,Z,5,*,=1,2,3,4.,生成元有,:2,3.,解 对于,a,=2,有,2,1,=2,2,2=,2,2=4,2,3,=2,2,2=8=3,2,4,=2,2,2,2=16=1.,Z,5,*,=1,2,3,4=2,4,2,1,2,3,2,2,.,请验证生成元,3,的情形,24,对于,a,=3,有,3,1,=3,3,2,=4,3,3,=2,3,4,=1.,Z,5,*,=1,2,3,4=3,4,3,3,3,1,3,2,.,25,循环群,定理设,G,是一个,n,阶循环群,则,G,恰有,(,n,),个生成元,.,如果,a,是,G,的一个生成元,则,a,r,也是,G,的生成元的充分必要条件是,:gcd(,n,r,)=1.,26,例,10,求,(,Z,12,),的全部生成元,.,提示,:,1,是一个生成元,.,27,解,:,1,是一个生成元,.,满足,gcd(12,r,)=1,的,r,:1,5,7,11.,Z,12,的生成元有,:1,1=1,5,1=5,7,1=7,11,1=11.,28,求出循环群,(,Z,p,),和,(,Z,p,*,),的全部生成元,.,从每个群中取出一个生成元,把该群中的全部元素表示成生成元的倍数,(,或方幂,),的形式,.,其中,(1),p,=7;(2),p,=13.,29,阿贝尔小传,阿贝尔,(N.H.Abel)1802,年,8,月,5,日出生于挪威,.,16,岁开始学习牛顿、欧拉、拉格朗日和高斯的经典数学著作,.,19,岁时,他解决了一个让一些著名数学家烦脑了数百年的难题,.,他证明了虽然一元二次、三次甚至四次方程都有求根公式,但是对于一般的五次方程却不存在这样的求根公式,.,他对于五次方程求解问题的解决为近世代数的创立做出了基础性的工作,.,30,此外,阿贝尔还在椭圆函数论、椭圆积分、阿贝尔积分和无穷级数等方面做出过杰出的贡献,.,1829,年,4,月,6,日,阿贝尔死于肺结核,年仅,27,岁,.,1872,年,若尔当,(C.Jordan),引入了阿贝尔群这一术语,以纪念这位英年早逝的天才数学家,.,31,有限环,定义 设,R,是一个非空集合,.,如果在,R,上定义了两个代数运算,“+”(,称为加法,),和,“,”,(,称为乘法,),并且满足,:,(R1)(,R,+),构成一个交换群,;,(R2),乘法结合律,:,即对所有的,a,b,c,R,有,(,a,b,),c,=,a,(,b,c,);,(R3),乘法对加法的分配律,:,即对所有的,a,b,c,R,有,a,(,b,+,c,)=,a,b,+,a,c,(,b,+,c,),a,=,b,a,+,c,a,则称,R,关于运算,“,+”,和,“,”,构成一个环,(ring),记为,(,R,+,).,32,注,1:(,R,+),是一个交换群,称为,R,的加法群,.,环,R,的加法单位元称为环的零元,记为,0.,环,R,的元素,a,的加法逆元称为,a,负元,记为,-,a,.,注,2:,如果环,R,的乘法还满足交换律,则称,R,为交换环,.,33,注,3:,如果环,R,中存在元素,e,使对任意的,a,R,有,a,e,=,e,a,=,a,则称,R,是一个有单位元的环,并称,e,是,R,的乘法单位元,(unit).,如果环,R,有单位元,则,R,的单位元是唯一的,.,环,R,的乘法单位元记为,e,或,1.,34,注,4:,设环,R,有单位元,e,a,R,如果存在,b,R,使,a,b,=,b,a,=,e,则称,a,是,R,的一个可逆元,(invertible element),并称,b,是,a,的逆元,(inverseelement),记为,b,=,a,-,1,.,一个环中,可能有些元素有逆元,而其它元素没有逆元,.,35,例,4.1.2.1,整数环,(,Z,+,);,有理数环,(,Q,+,);,实数环,(,R,+,);,复数环,(,C,+,).,例,4.1.2.2,设,m,Z,+,Z,m,=0,1,m,-1,则,(,Z,m,),是一个有单位元的交换环,.,称为模,m,剩余类环,(residue class ring).,36,有限域,定义,设,(,F,+,),是一个环,.,如果,F,有乘法单位元,1,0,的,且每个非零元都是可逆的,则称,(,F,+,),是一个域,(field).,进一步,如果,F,是有限集,则称,(,F,+,),是一个有限域,(finite field),也称为伽罗华域,(Galois field).,37,例,有理数域,(,Q,+,);,实数域,(,R,+,);,复数域,(,C,+,).,例,4.1.2.2,设,p,Z,+,是素数,Z,p,=0,1,p,-1,则,(,Z,p,),是一个有限域,.,38,定理,(1),每个有限域的阶一定是素数的幂,:,p,n,.,含有,p,n,个元素的有限域记为,GF,(,p,n,).,(2),任给素数,p,和正整数,n,一定存在阶为,p,n,的有限域,.,(3),同阶的有限域是同构的,.,(4),令,GF,(,p,n,)*,表示,GF,(,p,n,),的全体非零元的集合,则,GF,(,p,n,)*,关于乘法是一个,p,n,-1,阶循环群,.,39,含有,p,n,个元素的有限域只有一个,.,当,n,=1,时,GF,(,p,)=(,Z,p,)=,F,p,称为素域,.,40,伽罗瓦,(.Galois),法国数学家,1811,年,10,月,25,日出生于巴黎,.16,岁开始自学勒让德、拉格朗日、高斯和柯西等大师的经典数学著作和论文,.18,岁时,他完成了第一篇代数方程的重要论文,.,在,1828,年到,1830,年之间,他得到了后来被称为,“,伽罗瓦理论,”,的重要结论,.,1832,年,5,月,30,日,伽罗瓦由于政治和爱情的纠葛在决斗中被人射中,次日不幸去世,死时不满,21,岁,.,41,伽罗瓦提出的,“,伽罗瓦域,”,、,“,伽罗瓦群,”,和,“,伽罗瓦理论,”,是近世代数所研究的重要课题,他的工作是,19,世纪数学中最杰出的成就之一,.,伽罗瓦理论是代数学发展中的一个里程碑,.,伽罗瓦生前并未获得应有的荣誉,他投出的研究论文未被接受发表,.,直到,1846,年,著名数学家刘维尔解读了伽罗瓦的研究手稿,给出了注释,才在,纯粹与应用数学,上发表,.,42,多项式环与有限域,多项式环的基本性质,设,F,是一个有限域,表达式,f,(,x,)=,a,n,x,n,+,a,n,-1,x,n,-1,+,a,1,x,+,a,0,(,a,i,F,i,=0,1,n,-1),称为有限域,F,上的一个多项,(polynomial),x,称为未定元,(indeterminate).,43,多项式的次数,(degree):,如果,a,n,0,则称,f,(,x,),的次数为,n,记为,:deg(,f,(,x,)=,n,deg(0)=-,.,首一多项式,(monic polynomial):,a,n,=1,的多项式,.,多项式的加法,“,+”,与乘法,“,”.,用,F,x,表示有限域,F,上的全体多项式集合,.,44,定理 任给两个多项式,f,(,x,),g,(,x,),F,x,一定存在唯一的,q,(,x,),和,r,(,x,),满足,:,f,(,x,)=,q,(,x,),g,(,x,)+,r,(,x,)deg(,r,(,x,)deg(,g,(,x,).,q,(,x,),称为商式,r,(,x,),称为余式,.,45,已知,F,5,上的多项式,f,(,x,)=2,x,5,+,x,4,+4,x,+3,g,(,x,)=3,x,2,+1,求商式与余式,.,解,:,使用长除法,(long division),商式,q,(,x,)=4,x,3,+2,x,2,+2,x,+1,余式,r,(,x,)=2,x,+2.,46,