密码学基础群(循环群,生成元)

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,群的概念,定义,设,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,).,1,注,1:(G2),中的元素,e,称为群,G,的单位元,(unit element),或恒等元,(identity).,群,G,的单位元是唯一的,.,注,2:(G3),中的元素,b,称为元素,a,的逆元,(inverse).,元素,a,的逆元是唯一的,记为,a,-,1,.,即有,a,a,-,1,=,a,-,1,a,=,e,2,有限群,交换群,如果群,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,+,),是群,.,3,群的概念,例,1,设,G,=1,-1,i,-i,则,(,G,),是一个有限交换群,.,元素,a,1,-1,i,-i,逆元,a,-1,1,-1,-i,i,4,例,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,5,有时把交换群,(,G,),记为,(,G,+),称为,“,加群,”.,把运算,“,”,称为,“,加,”,法,运算结果记为,:,a,b,=,a,+,b,称为,a,与,b,的,“,和,”;,单位元称为,“,零元,”,记为,“,0”;,a,G,的逆元称为,G,的负元,记为,:“-,a,”,即有,a,+(-,a,)=0.,6,例,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).,7,例,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,8,群的概念,有时把群(G,)记为(G,),称为“乘群”.,把运算“”称为“乘”法,运算结果记为:ab=ab,称为a与b的“积”;,运算符号通常省略,简记为:ab=ab=ab.,单位元记为:e=1.,9,例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).,10,特别地:取m=5,有Z,5,*=1,2,3,4,111 mod 5 所以1的逆元素是1,求出其他元素的逆元素,11,元素,a,1,2,3,4,逆元,a,-1,1,3,2,4,元素,a,的逆元,12,群的幂,设,(,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,.,13,加群的倍数,设,(,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,.,14,群元素的阶,设,G,是一个群,e,是,G,的单位元,a,G,如果存在正整数,r,使得,a,r,=,e,则称,a,是有限阶的,否则称,a,是无限阶的,.,如果,a,是有限阶的,则把满足,a,r,=,e,的最小正整数,r,称为,a,的阶,(order),记为,ord,a,=,r,.,如果,a,是无限阶的,则记,ord,a,=,.,15,计算群,(,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.,下面，请求出各元素的阶,16,a,1,2,3,4,a,的阶,1,4,4,2,元素,a,的阶如下,17,例,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,18,设,G,是一个群,如果存在,a,G,使得,G,=,a,1,a,2,=,则称,G,是一个循环群,(cyclic group),并称,a,是的一个生成元,(generator).,如果,G,是一个,n,阶循环群,则,G,=,a,1,a,2,a,n,=.,提示:计算时请从,a,1,开始,19,如果,G,是一个,n,阶循环群,且元素,a,G,的阶,=,群,G,的阶,则,a,是,G,的一个生成元,.,例,8,设,m,Z,+,Z,m,=0,1,m,-1,则,(,Z,m,),是,m,阶循环群,.1,是一个生成元,.,20,特别地,:,取,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.,注意,:,循环群的生成元不是唯一的,!,21,循环群,定理 设,p,是素数,则,(,Z,p,*,),是,p,-1,阶循环群,.,Z,p,*,的生成元,a,称为,Z,的一个模,p,元根,(primitive root).,22,群,(,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的情形,23,对于,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,.,24,循环群,定理设,G,是一个,n,阶循环群,则,G,恰有,(,n,),个生成元,.,如果,a,是,G,的一个生成元,则,a,r,也是,G,的生成元的充分必要条件是,:gcd(,n,r,)=1.,25,例,10,求,(,Z,12,),的全部生成元,.,提示:,1,是一个生成元,.,26,解:,1,是一个生成元,.,满足,gcd(12,r,)=1,的,r,:1,5,7,11.,Z,12,的生成元有,:1,1=1,5,1=5,7,1=7,11,1=11.,27,求出循环群,(,Z,p,),和,(,Z,p,*,),的全部生成元,.,从每个群中取出一个生成元,把该群中的全部元素表示成生成元的倍数,(,或方幂,),的形式,.,其中,(1),p,=7;(2),p,=13.,28,阿贝尔小传,阿贝尔,(N.H.Abel)1802,年,8,月,5,日出生于挪威,.,16,岁开始学习牛顿、欧拉、拉格朗日和高斯的经典数学著作,.,19,岁时,他解决了一个让一些著名数学家烦脑了数百年的难题,.,他证明了虽然一元二次、三次甚至四次方程都有求根公式,但是对于一般的五次方程却不存在这样的求根公式,.,他对于五次方程求解问题的解决为近世代数的创立做出了基础性的工作,.,29,此外,阿贝尔还在椭圆函数论、椭圆积分、阿贝尔积分和无穷级数等方面做出过杰出的贡献,.,1829,年,4,月,6,日,阿贝尔死于肺结核,年仅,27,岁,.,1872,年,若尔当,(C.Jordan),引入了阿贝尔群这一术语,以纪念这位英年早逝的天才数学家,.,30,有限环,定义 设,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,+,).,31,注,1:(,R,+),是一个交换群,称为,R,的加法群,.,环,R,的加法单位元称为环的零元,记为,0.,环,R,的元素,a,的加法逆元称为,a,负元,记为,-,a,.,注,2:,如果环,R,的乘法还满足交换律,则称,R,为交换环,.,32,注,3:,如果环,R,中存在元素,e,使对任意的,a,R,有,a,e,=,e,a,=,a,则称,R,是一个有单位元的环,并称,e,是,R,的乘法单位元,(unit).,如果环,R,有单位元,则,R,的单位元是唯一的,.,环,R,的乘法单位元记为,e,或,1.,33,注,4:,设环,R,有单位元,e,a,R,如果存在,b,R,使,a,b,=,b,a,=,e,则称,a,是,R,的一个可逆元,(invertible element),并称,b,是,a,的逆元,(inverseelement),记为,b,=,a,-,1,.,一个环中,可能有些元素有逆元,而其它元素没有逆元,.,34,例,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).,35,有限域,定义,设,(,F,+,),是一个环,.,如果,F,有乘法单位元,1,0,的,且每个非零元都是可逆的,则称,(,F,+,),是一个域,(field).,进一步,如果,F,是有限集,则称,(,F,+,),是一个有