信息安全导论-5密码学数学基础省名师优质课赛课获奖课件市赛课一等奖课件.ppt

单击此处编辑母版标题样式,*,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。感谢您,信息安全导论,第五讲,密码学技术中数学基础,华中科技大学图象所,信息安全研究室,Dr.Zuxi Wang,第1页,2024/11/25 周一,1,密码学,是研究密码系统或通信安全一门学科，分为密码编码学和密码分析学。,密码编码学,是使得消息保密学科，从事此行称为密码编码者。,密码分析学,（密码破译学）是研究加密消息破译学科，从事此行称为密码分析者。精于此道人被称为密码学家，当代密码学家通常是理论数学家。,第2页,2024/11/25 周一,2,密码学是一门交叉学科，它很大程度上是应用数学学科。,密码学中包括数论、代数、概率论、组合数学、计算复杂理论等各种数学知识。,还包括信息论学科知识。,密码学所包括知识十分辽阔，这里仅介绍部分数学基本知识。,第3页,2024/11/25 周一,3,数论基础,素数,同余、模运算,中国剩下定理,Euclean,算法,Fermat,定理、,Euler,定理,素性检验,因子分解,离散对数,第4页,2024/11/25 周一,4,整除,、,素数,记整数集合,Z=,-3,-2,-1,0,1,2,3,整除,设,a,bZ，a0，,假如存在,mZ，,使得,b=ma，,则称,a,整除,b，,以,a|b,表示，,a,是,b,一个,因子,或,约数,。,假如没有任何,m，,使得,b=ma，,则称,a,不能整除,b,记,ab，,此时有,a=mb+r,且0,r1,被称为,素数,是指,p,因子仅有1，-1，,p,，,-,p,。,不然，称为,合数,。,第5页,2024/11/25 周一,5,整除基本性质,a|a;,b0,，b|,0,;,If a|b,b|c,then a|c;,if,a|1,then,a=1,;,if,a|b,and b|a,then,a=b,;,if,b|g,and,b|h,then,b|(mg+nh),for any integers,m,and,n,注意,:if,a=0 mod n,then,n|a,第6页,2024/11/25 周一,6,互素与最大条约数,最大条约数,（,最大公因子,）,：,若,a,b,c,Z，,假如,c,a,，,c,b,，,称,c,是,a,和,b,条约数,。正整数,d,称为,a,和,b,最大条约数,(,记,d,=gcd(,a,b,),或,(,a,b),),，假如它满足:,d,是,a,和,b,条约数。,对,a,和,b,任何一个条约数,c,有,c,d,。,等价定义形式是：,gcd(,a,b,)=max,k,:,k,a,，,k,b,若,gcd(,a,b,)=1，,称,a,与,b,是,互素,。,第7页,2024/11/25 周一,7,最小公倍数,最小公倍数,a,b,倍数中最小者称为,a,b,最小公倍数,，记为：,lcm(,a,b,),a,b,不全为0，有,ab,=gcd(,a,b,)lcm(,a,b,).,注意,：对有限个整数,a,1,a,2,a,n,也可定义最大条约数,gcd(,a,1,a,2,a,n,),和最小公倍数,lcm(,a,1,a,2,a,n,).,第8页,2024/11/25 周一,8,带余除法,带余除法,：,a,Z,m,0，,可找出两个唯一确定整数,q,和,r,使,a,=,qm+r,0,r,P,2,P,3,P,t,是素数，其中,i,0,整数。,第10页,2024/11/25 周一,10,当前没有可用于整数分解有效算法,。,对于整数,a,b,(,a,b,2)，,a,b,素数分解式分别为：,，其中,e,i,，,f,i,0,ti1,，则有：,第11页,2024/11/25 周一,11,带余除法中，,a,Z,，,m,0,，,a=qm+r,，,0,r,1）,分成一些两两不交,等价类,（,剩下类,）,。,2,、整数模,m,同余类共有,m,个，他们分别为,mk,+0,mk,+1,mk,+2,mk,+(,m,-1);,k,z，,每一个算一类，,每一类,都能够选一个,代表元,，普通选这一类中,最小非负整数,。于是称0,1,2,m-1,为,标准完全剩下系,。其中,与,m,互素,剩下类组成模,m,简约剩下系,。,Z,模12标准完全剩下系为：0,1,2,3,4,5,6,7,8,9,10,11,第13页,2024/11/25 周一,13,Modulo 7 Example,.,-21-20-19-18-17-16-15,-14-13-12-11-10 -9 -8,-7 -6 -5 -4 -3 -2 -1,0 1 2 3 4 5 6,7 8 9 10 11 12 13,14 15 16 17 18 19 20,21 22 23 24 25 26 27,28 29 30 31 32 33 34,.,第14页,2024/11/25 周一,14,3,、模运算,：对于某个固定模,m,同余式能够象普通等式那样相加相减和相乘：,a,(mod,m,),b,(mod,m,)=(,a,b,)(mod,m,),a,(mod,m,),*,b,(mod,m,)=,a*b,(mod,m,),例：,由同余式演算证实5,60,1是56倍数，2,23,1是47倍数。,解：,注意5,3,=12513(,mod56),于是有5,6,1691(,mod56),对同余式两边同时升到10次幂，,即有56(5,60,-1)。,其次,注意,2,6,=64-30(,mod47),于是,2,23,=(2,6,),3,2,5,=(2,6,2,6,)2,6,2,5,900*(-30)*(32),mod(47),(7),*,(-30)*(32)(mod47),1(mod47),于是有,47(2,23,-1),第15页,2024/11/25 周一,15,Modulo 8 Example,第16页,2024/11/25 周一,16,4,、,定理,：(,消去律,)对于,ab,ac,(mod,m,),来说，若最大公因子,gcd,(,a,m,)1,（即,a,与,m,是,互素），,则,b,c,(mod,m,),加法消去律,：,a+b,a+c,(mod,m,)，,有,b,c,(mod,m,).,5,、,一次同余方程,ax,b,(mod,m,)，,这个方程有没有解，相当于问有没有那样一个整数,x,，,使得对于某个整数,y,来说，有,ax+my=b,定理,：记最大公因子(,a,m,)=,d,，则同余方程,ax,b,(mod,m,),有解充分必要条件是,d,b,。,当这个条件满足时，恰有,d,个模,m,同余类中整数是上述方程解。,证实：略。（从,ax+my=b,入手）,第17页,2024/11/25 周一,17,6,、,整数环,z,模正整数,m,得到,剩下类集合,能够记为,z,m,(,或,z/(m),z,m,=0,1,m-1,在,3,、中已说明,z,m,对剩下类加法，乘法是封闭，可列出它们加乘表。我们称,z,m,为,剩下类环,（或,同余类环,）,7,、在,整数环,z,中是没有零因子，即两个非零整数乘积一定不等于0，不过,剩下环,则不然。,例,z,12,中：3*4=12=0,说明，,z,m,中元素可分为两类，,一类是零因子,，即若,z,m,0,，存在,z,m,且,0，,有,*=0，,则称,，,都为,z,m,中零因子。,另一类是可逆元,，即若,z,m,，,存在,z,m,，,使,*=1，,此时,互为各自逆元，记,-1,=；,-1,=,第18页,2024/11/25 周一,18,定理,：剩下类环,z,m,中元素,=,a,为,z,m,可逆元,最大条约数(,a,m,)=1,要证实这个定理，只需证实以下引理：,引理,：任意两个整数,a,和,b,都有一个最大条约数，这么一个最大条约数,d,能够表示成,a,b,二数关于整系数线性组合，即有,s,tz，,使,dsa,tb,。,证实,：不妨设,b,0，,用,辗转相除法,，先用,b,去除,a，,得,a=q,1,b+r,1,0r,1,b;(1),假如,r,1,=0，,停顿，不然再用,r,1,去除,b，,得,b=q,2,r,1,+r,2,0r,2,r,1,;(2),假如,r,2,=0，,停顿，不然再用,r,2,去除,r,1,，,得,r,1,=q,3,r,2,+r,3,;0r,3,r,2,;(3),等等，这么一直进行下去，可得一系列关系式：,r,k-3,=q,k-1,r,k-2,+r,k-1,0r,k-1,r,k-2,;(k-1),r,k-2,=q,k,r,k-1,+r,k,0r,k,r,2,r,3,r,4,r,k,0,是严格递降一串非负整数，故最终总会出现余数为0情形：,r,k-1,=q,k+1,r,k,(k+1),所以，进行有限步必停顿，此时,d,=r,k,=(,a,b,),成立,，这是因为,1).可知,r,k,为,a,和,b,条约数,，只要按倒序分析自然有此结论。,2).,a,和,b,任何一个条约数,c,都是,r,k,约数,，只要按正序分析，自然可知。,为证定理后一部分，将式(1)做移项有,r,1,=s,1,a+t,1,b（,其中,s,1,=1,t,1,=-q,1,）,再将式(2)右端经过移项变为,r,2,=s,2,a+t,2,b,这么一直下去，最终得,d=r,k,=s*a+t*b,s,tz.,第20页,2024/11/25 周一,20,例子,：求(180，252)，并将他表示为180和252这两个数一个带整系数线性组合。,解：252=1*180+72(1),180=2*72+36 (2),72=2*36(3),得(180,252)=36，同时有,72=252-1*180 (1,),由(2)得,36=180-2*72 (2,)将(1,)代入(2,)，即得 36=180-2*(250-180)=3*180-2*252,第21页,2024/11/25 周一,21,中国剩下定理,例子：（孙子算经）今有物不知其数：三三数之余二；五五数之余三；七七数之余二。问物几何？,答曰：二十三。,232*70+3*21+2*15(,mod 105),（,口诀：三人同行七十稀，五树梅花廿一枝，七子团圆月正半，除百零五便得知。）,问，70，21，15怎样得到,？,原问题为：,求解同余方程组,第22页,2024/11/25 周一,22,注意,：若,x,0,为上述同余方程组解，则,x,0,=x,0,+105*k(kz),也为上述同余方程组解。有意义是，解题口诀提醒我们先解下面三个特殊同余方程组,(1)(2)(3),特殊解,=?=?=?,以方程（1）为对象，相当于解一个这么同余方程 35,y,1(mod 3)，,为何呢？,原因是，从（1）模数及条件知，,x,应是35倍数，于,是能够假设,x,35,y,，,有,第23页,2024/11/25 周一,23,35,y1(mod 3),相当于2,y1(mod 3),解出,y,=2（mod3）,于是,x,35*2,(mod(3*35),70(mod105),类似地得到（2）、（3）方程模105解21、15。,于是有,得,第24页,2024/11/25 周一,24,中国剩下定理,：设自然数,m,1,m,2,m,r,两两互素，并记,M=m,1,m,2,m,r,，,则同余方程组,在模,M,同余意义下有唯一解。,第25页,2024/11/25 周一,25,证实：考虑方程组，,(1=,i=r),因为诸,m,i,(1=i1,时，它值,(n),等于比,n,小而与,n,互素正整数个数。,以,n24,为例，比24小而与24 互素正整数为：1,5,7,11,13,17,19,23。所以，我们有,(24)8。,若,p,为素数，则,(p)p-1。,若,p，q,都为素数且,pq，,此时有,(pq)(p)(q)=(p-1)(q-1),证实,：考虑,z,pq,剩下类集合是0，1，2，（,pq-1）,集合中与,pq,不互素元素子集为,p,2p,(p-1)q,和子集,q,2q,(p-1)q,以及0，于是若设,npq，,有,(n)=,pq-(q-1)+(p-1)+1=,(p-1)(q-1)=(p)(q),.,例,：,(21)=(3*7)=(3)(7)=2*6=12.,第32页,2024/11/25 周一,32,若,m,1,m,2,互素，则,(m,1,m,2,)(m,1,)(m,2,).,设,n=p,1,e1,p,2,e2,p,r,er,，,其中,p,1,p,2,p,r,为互异素数，则,(n),=p,1,e1-1,p,2,e2-1,p,r,er-1,(p,1,-1)(p,2,-1)(p,r,-1),=n(1-1/p,1,)(1-1/p,2,)(1-1/p,3,)(1-1/p,r,),Euler,公式,证实：考虑1/,n,2/n,n/n，,然后化简成既约分数，分母为,d,一类分数有,(d),个，于是,欧拉定理（,Euler）,：,若整数,a,与整数,n,互素,，,则,a,(n),1(mod n)。,证实,：设小于,n,而和,n,互素,(n),个正整数为,r,1,r,2,r,3,r,(n),(1),第33页,2024/11/25 周一,33,他们是模,n,两两互不一样余,。,对每一个定数,i,来说，因为,a,和,r,i,都与,n,互素，所以(,ar,i,n)=1，,所以,ar,i,同余于（1）中某个,r,i,即,ar,i,r,i,(mod n)，1i(n),而且当,ij,时有,ar,i,/,ar,j,(mod n).,于是,为 置换.所以有,由(,r,i,n)=1,所以,Remarks,：,1,*,.,np,时，(,a,p)=1,有,a,p-1,1(mod p),为,Fermat,定理,！,而对任意,a，,有,a,p,a(mod p)（,Fermat,）,2,*,.易见,a,(n)+1,a(mod n),3,*,.,若,n=pq，p,与,q,为相异素数，取0,mn，,若(,m,n)=1，,有,m,(n)+1,m(mod n)，,也即,m,(p-1)(q-1)+1,m(mod n).,第34页,2024/11/25 周一,34,4,*,.对于3中，若(,m,n)p,或,q，,也一样有,m,(n)+1,m(mod n),5,*,.,由 (,m,(n),),k,1,k,(mod n),知,m,k(n),1(modn)，,深入,m,k(n)+1,m(mod n),m,k(p-1)(q-1)+1,m(mod n),第35页,2024/11/25 周一,35,素性检验、因子分解,在许多加密算法中，需要随机选择一个或多个非常大素数，所以必须确定一个给定大数是否是素数。,素性检验(测试),当前还没有简单有效方法处理该问题。,Miller,和,Rabin,提出一个算法，其利用了,Fermat,定理。该算法产生数不一定数素数，但令人诧异是，其产生数几乎能够必定是素数。,第36页,2024/11/25 周一,36,素性检验、因子分解,RSA,算法安全性以对大整数进行素数分解困难性为基础，即无法在多项式时间内对于一个足够大整数进行分解。一旦这个难题被破解，则RSA算法安全性便不复存在。,一些具代表性因子分解算法包含：,二次筛法,p-1因子分解方法,是更为有效椭圆曲线方法基础,数域筛法等,第37页,2024/11/25 周一,37,强素数,许多密码算法关心,强素数,。,设,nZ，p,和,q,是素数，而且,n=pq。,当,p，q,满足以下特征时，称之为,强素数,。,Gcd(p-1,q-1),比较小；,p-1和q-1都有大素因子（分别记为p*和q*）；,p*-1和q*-1都有大素因子；,p+1和q+1都有大素因子；,(p-1)/2和(q-1)/2都是素数。,假如素数,p,含有特征,则它们一定含有特征和.,此时，即使采取一些特殊因子分解方法，对整数,n,进行因子分解也非常困难。,第38页,2024/11/25 周一,38,为了增加密码算法安全性，提议使用长度大而且含有随机性结构强素数，其中，素数长度比其结构特点更为主要。,不过，从因子算法对整数进行分解概率角度考虑，强素数与其它素数相比并没有明确优势。,第39页,2024/11/25 周一,39,代数基础,群,、,环,、,域,、,布尔代数,概述,群、环、域,基本概念,有限域,GF(pn),多项式算术,布尔代数与布尔函数,第40页,2024/11/25 周一,40,概 述,有限群、有限域、布尔函数等在密码技术和应用中越来越主要。,cryptography,AES,Elliptic Curve,IDEA,Public Key,将从抽象代数群、环、域基本概念开始介绍。,第41页,2024/11/25 周一,41,群（,Group）,代数系统,：,一个集合以及定义在其上一组运算一起组成一个,代数系统,。,群（,group）,是一个代数系统,，它仅有一个二元运算,*,（因为是代数系统，所以运算封闭性满足），并满足:,结合律:,(,a,*,b),*,c=a,*,(b,*,c),含有单位元,e,:,e,*,a=a,*,e=a,每一元,a,有逆元,a,-1,:,a,*,a,-1,=e,假如满足交换律:,a,*,b=b,*,a,则形成一个,交换群,(,commutative group),也叫阿贝尔群,(,abelian group).,Remark,:,在不引发歧义下，经常将运算符号省略。a,*,b=ab,第42页,2024/11/25 周一,42,例1,和,不是群。,、,和,都是群。,例2,设有,Z,4,=0,1,2,3，,模4加法运算 定义为,则,组成一个群。,0 1 2 3,0,1,2,3,0 1 2 3,1 2 3 0,2 3 0 1,3 0 1 2,Examples:,第43页,2024/11/25 周一,43,Examples:,是一个交换群，也叫加群。+是关于模m加法；,，是关于模m乘法。当m是素数时，它组成一个乘法交换群；但当m不是素数时，它不组成群。,第44页,2024/11/25 周一,44,循环群（,Cyclic Group）,群元素,幂,example,:,a,3,=a,*,a,*,a,a,k,=a,*,a,*,*,a(k,个,a,相乘，,k,正整数),要求:,e=,a,0,，a,-k,=a,-1,*,a,-1,*,*,a,-1,=(,a,-1,),-k,(k,个,a,-1,相乘，,k,正整数),对任意整数,m,n,a,m,*,a,n,=a,m,+,n,(a,m,),n,=a,mn,a,-,n,=(a,-1,),n,=(a,n,),-1,.,群中任何元都是某个元,g,幂，称群为,循环群,，,g,称为其一个,生成元,(,generator)。,i.e.,对群中任一元,b,存在,k,使,b=,g,k,.,以,g,为生成元循环群记为,G=.,称为由,g,生成循环群.,第45页,2024/11/25 周一,45,对任意负整数 ,按照群中逆元表示方法,例3,群,是循环群，1是生成元，1,0,=0，对任意正整数,n，n=1+1+1，,按照群中元素幂表示方法,n=1,n,.,例4,例2中群,是循环群，1是其生成元，3也是其生成元。,因为1,0,=0，1,1,=1，1,2,=1,4,1=,res,4,(2)=2,1,3,=1,2,4,1=2,4,1=res,4,(3)=3,又3,0,=0，3,1,=3，3,2,=3,4,3=,res,4,(6)=2,3,3,=3,2,4,3=2,4,3=res,4,(5)=1,第46页,2024/11/25 周一,46,例5,设,G=a,b,c,e,，*,是,G,上二元运算，,*,e a b c,e,a,b,c,a e c b,b c e a,c b a e,e a b c,a,*,a=b,*,b=c,*,c=e,*,e=e ,a,*,b=b,*,a=c,b,*,c=c,*,b=a，a,*,c=c,*,a=b,是一阿贝尔群，但它不是循环群，普通称这个群为,Klein,四元群,。,第47页,2024/11/25 周一,47,群阶和元素周期,设,是一个群，假如,G,是有限集，则称,是,有限群,，,G,中元素个数称为群,阶,；若,G,是无限集，则称,是,无限群,。,设,是一个群，,a G，,若存在正整数,r，,使得,a,r,=e，,则称元素,a,含有,有限周期,。使,a,r,=e,成立最小正整数,r,称为,a,周期,。假如对于任何正整数,r，,都有,a,r,e，,则称,a,周期为无限,。,第48页,2024/11/25 周一,48,群阶和元素周期,Examples,在群,中，单位元1周期为1,-1周期为2.,（-1）,2,=（-1）,4,=（-1）,6,=,=1,群,中，1,4,=1,3,4,1=3,4,1=,res,4,(4)=0；,2,1,=2，2,2,=2,4,2=,res,4,(4)=0；,3,4,=3,3,4,3=1,4,3=,res,4,(4)=0。,生成元1和3周期均为4，循环群,阶也为4。,循环群,生成元1和1，其周期均为无限，群,是一个无限阶循环群。,第49页,2024/11/25 周一,49,群部分性质,消去律,：,设,是一个群，则对任意,a,b G，,（1）,存在唯一元素,xG，,使,a,*,x=b；,（2）,存在唯一元素,yG，,使,y,*,a=b。,设,是一个群，则对任意,a,b,cG,（,1,）,若,a,*,b=a,*,c,则,b=c；,（,2,）,若,b,*,a=c,*,a,，,则,b=c,。,第50页,2024/11/25 周一,50,群部分性质,求逆,:,设,是一个群，则对任意,a,b,a,1,a,2,a,k,G,(a,*,b),-1,=b,-1,*,a,-1,;,(a,1,*,a,2,*,*,a,k,),-1,=a,k,-1,*,*,a,2,-1,*,a,1,-1,.,关于元素周期,:,群,中元素,a,若含有有限周期,r,，,则当且仅当,k,是,r,整数倍时，,a,k,=e.,群中任一元素与它逆元含有相同周期。,在有限群,中，每个元素均含有有限周期，且周期不超出群,阶。,结论对无限群不成立。如群,.,第51页,2024/11/25 周一,51,群部分性质,设,是一由元素,g,生成循环群，则,若,g,周期为,n，,则,是一个阶为,n,有限循环群；,若,g,周期为无限，则,是一个无限阶循环群。,第52页,2024/11/25 周一,52,群部分性质,Examples,群,中单位元,0,周期是,1,；,1,和,3,周期均为,4,；,2,周期为,2,，群,阶,4.,设,是一个群，且对于任意,a,bG，,有,(a,*,b),2,=a,2,*,b,2,则,是阿贝尔群。,设,Z,6,=0,1,2,3,4,5,6,是模6加法，定义为：,a,6,b=res,6,(a+b)，,是一个群。,给出其单位元；各元素逆元；各元素周期。,第53页,2024/11/25 周一,53,设,是一个群，若,是,子代数，单位元,e,H，,且对于任意,a,H，,有,a,-1,H，,则称,是,子群,。,非空子集,H,关于,G,运算,*,组成子群，必须满足：,封闭性：,H,关于,*,封闭，,a,bH，,有,a*b H;,单位元：,G,单位元,eH;,可逆性：任意,aH，,有,a,-1,H.,Example,:,对于任意整数,m,，,若令,I,m,=,mi,:,i,I.,则,均组成,子群。,子群（,Subgroup）,第54页,2024/11/25 周一,54,若,是,子群，则,也是群。,设,是一个群，,H,是,G,非空子集，若,也是群，则称,是,子群。,（,子群等价定义,）,设,是群，,H,是,G,非空子集，若,(1)对于任意,a,bH,，,有,a,*,bH,；,(2),对任意,aH,，,有,a,-1,H,，,则,是,子群。,子群（,Subgroup）,第55页,2024/11/25 周一,55,设,是群，,H,是,G,非空子集，,若对于任意,a,bH,，,有,a,*,b,-1,H，,则,是,子群。,设,是一,有限群,，若,是,子代数，则,是,子群。,即：若对于任意,a,bH,，,有,a,*,bH，,则,是,子群（,H,有限且关于运算封闭就组成子群,）。,设,是一个群，若,是,有限子代数,，则,是,子群。,子群（,Subgroup）,第56页,2024/11/25 周一,56,子群（,Subgroup）,Examples,设,是一个群，,a,是,G,中任一元素，令,H,是,a,全部整数次幂集合，则,H,对于,G,运算组成,子群。显然,是由元素,a,生成一个循环群。,设,是一个群，定义,G,子集,H=,h,:,对任意,x,G,h,*,x,=,x,*,h,，H,对于运算,*,组成,子群。,第57页,2024/11/25 周一,57,陪集（,coset）、,正规子群（,normal subgroup）,H,是,G,子群，,a,属于,G，aH=ah|h,属于,H,称为,G,一个关于,H,左陪集,（,a,所在陪集）。一样,Ha,组成一个,右陪集,。,对,a，aH,不一定等于,Ha。,假如对所以,a，,都有,aHHa，,则称,H,为,G,一个,正规子群,。称,aH,或,Ha,为,陪集,。,第58页,2024/11/25 周一,58,拉格朗日(,Lagrange),定理,陪集定理,：,G,关于,H,全部不用左（右）陪集组成,G,一个分划。,Lagrange,定理,：群,G,必为其子群,H,及其全部不相同陪集直和。,推论,：有限群阶必为其子群阶整数倍。,素数阶群只有平庸子群（群本身与单位元）,第59页,2024/11/25 周一,59,群同态与同构,h:G,1,G,2,群间一个映射，假如,h,保持群运算，即：,a,b of G，,有,h(ab)=h(a)h(b)，,则称,h,为群,G,1,G,2,间一个,同态映射,，简称,同态,(,homomorphism),。,若同态,h,同时是一个双射，那么称,h,为一个,同构映射,，简称,同构,(,isomorphism),。这是称两群,G,1,G,2,是,同构,。,从代数结构角度看，同构群含有相同代数结构，被视为同一群。,第60页,2024/11/25 周一,60,商群（,Quotient group）,群,G,正规子群,H,与其全部不相同陪集在陪集乘法意义下组成一个群，称为,G,关于,H,商群,，记为,G/H。,f,:GG,群间一个同态映射，,ker,f,g:,f,(g)=e,e,为,G,单位元，即,ker,f,为,G,单位元,e,在,G,中原象集合。称,ker,f,为同态映射,f,核,。,同态基本定理,：设,G,为,G,关于同态映射,f,象，则有：,1.,ker,f,是,G,正规子群；,2.,G,与商群,G/ker,f,同构。,第61页,2024/11/25 周一,61,变换群（,Transform group）,集合,A,上若干双射（一一映射）对于映射复合运算组成一个群，称其为,A,上一个,变换群,。,一个集合,A,全部一一变换作成一个变换群。,任何一个群都与一个变换群同构。,第62页,2024/11/25 周一,62,置换群（,permutation group）,有限集,A,到直身一个双射称为,A,上一个,置换,。,A=n，,称,A,上置换为,n,阶置换,。,An，A,上全部,n,阶置换在置换乘积（映射复合操作）下组成一个群，称为,n,阶,对称群,(,Symmetric group)，,记为,S,n,。,S,n,任一子群，都称为一个,置换群,。,全部,n,阶偶置换（可分解为偶数个对换乘积置换）组成,S,n,一个子群，叫,交织群,(,Alternative group)，,记为,A,n,。,第63页,2024/11/25 周一,63,置换群（,permutation group）,对称群,S,n,阶为,n!，,交织群,A,n,阶为,n!/2。,凯莱(,Caylay),定理,：每一个有限群均同构于由群元素集合上一个置换群（,S,n,一个子群）,(,g,G，gf(g),f(g),为,G,上一个置换，,f(g)：,g,i,g,g,i,全体,f(g),组成,G,上置换群),第64页,2024/11/25 周一,64,群生成元系,G,是一个群，,S,是,G,一个非空子集,S,生成子群,H:G,包含,S,最小子群,记,H(S)。,S,生成子群,H,由,S,中元素及逆元任意乘积组成。,假如,G=(S)，,那么称,S,为群,G,一个,生成元系,(,Generator system or generator set),。,当,S1，Sa，,那么,S,生成,G,一个循环子群，,(S).,群生成元系通常不唯一。,第65页,2024/11/25 周一,65,对称群生成系,对称群,S,n,每个元都能够写成(12),(13),(1,n),这,n-1,个,对换,（2-循环置换）中若干个乘积。,S=,(12),(13),(1,n),是,S,n,一个生成元系。,Remark,：S,n,还有其它生成元系。,第66页,2024/11/25 周一,66,环（,Ring）,带两个运算（称加法和乘法）集合满足,:,关于加法+组成一个,abelian,群，,其单位元为0称为,零元,；,关于乘法 满足:,乘法封闭律；,满足结合律；,a(bc)=(ab)c,对加法分配律:,a(b+c)=ab+ac,则称,为一个,环,（,Ring,）,假如乘法是交换，则称环为,交换环,(,commutative ring),环中关于乘法假如有单位元，称之为环,单位元,。,第67页,2024/11/25 周一,67,子环,、,理想,、,剩下类环,子代数即为其,子环,。,R,子集关于,R,运算依然是环，称为,R,子环。,R,子环,I，,假如同时关于乘法还满足：,对,R,中任意元,r，I,中任意元,a，,有,ar,ra,均仍属于,I.,则称,I,为一个,理想,。,R,理想,I，,关于加法组成剩下类集合上关于模,I,加法和乘法组成环，叫,R,模,I,剩下类环,。记为,R/I.,第68页,2024/11/25 周一,68,环同态与同构,环,同态,与,同构,映射定义类似,群同态与同构,。,两个环之间映射假如保持分别,保持环运算,，就称为,环同态,假如同态是一一映射，就称为,同构,。,类似地有,同态基本定理,。,第69页,2024/11/25 周一,69,零因子,、,整环,若,ab=0,但,a,b,都不是,R,中零元,那么,a(b),均称为,左(右)零因子,.不然，称为,非零因子,.,无零因子环,:,假如,R,中,a,b,有,ab=o,那么必有,a=0 or b=0.,整环,（,domain,）,：,交换有,单位元,无零因子环，称为一个,整环,。,第70页,2024/11/25 周一,70,Example,:,整数集关于普通加法和乘法组成一个环且是一个,整环,.,是一个,交换环,，称为模,m,剩下类环。,当,m,是合数时，剩下类环,Z,m,中有,零因子,，,Z,m,中,a，,若(,a,m)=1,则,a,有逆元；当,m,是素数时，剩下类环,Z,m,是整环。,第71页,2024/11/25 周一,71,除环,、,域,一个环关于其乘法不一定有单位元，另外其任一元也不一定有乘法,逆元,。,假如一个环有单位元，而且任一非零元都有逆元，则称其为一个,除环,。,所以,是除环，它最少有一非零元，且,是加群；,是群。,一个除环，假如其关于乘法是交换，则称其为一个,域,（,Field,）,。,第72页,2024/11/25 周一,72,有限域,（,Galois Fields,）,有限域也叫,Galois,域，在密码学中有主要作用。,三个结论,：,每个有限域阶必为素数幂。,对任意素数,p,和正整数,n，,存在,p,n,阶域。,同阶有限域必同构。,于是：在同构意义下，,p,n,阶有限域有且只有一个，记为,GF(p,n,).,尤其地，经惯用到有限域,:,GF(p),称为,素域,GF(2,n,),第73页,2024/11/25 周一,73,Galois Fields GF(p),GF(p)是 0,1,p-1上关于模p加法、乘法组成有限域。,P为素数时，其中任意非零数都有逆元.,第74页,2024/11/25 周一,74,Example GF(7),第75页,2024/11/25 周一,75,GF(p),中乘法逆元算法,经过扩展,Euclidean,算法得到:,EXTENDED EUCLID(,m,b,),1.,(A1,A2,A3)=(1,0,m,);,(B1,B2,B3)=(0,1,b,),2.if,B3=0,return,A3=gcd(,m,b,);（,b mod m,没有逆,）,3.,if,B3=1,return,B3=gcd(,m,b,);B2=,b,1,mod,m,4.,Q=A3 div B3（,A3,除以,B3,商,）,5.,(,T1,T2,T3)=(A1 Q B1,A2 Q B2,A3 Q B3),6.,(A1,A2,A3)=(B1,B2,B3),7.,(B1,B2,B3)=(T1,T2,T3),8.goto,2,GF(p,n,),中乘法求逆类似（换成关于多项式除法）,第76页,2024/11/25 周一,76,Inverse of 550 in GF(1759),第77页,2024/11/25 周一,77,域上多项式,域,F,上,多项式,为形如：,表示式，其中,nN,a,i,F,i=1,2,n.,若,a,n,0,称,n,为该多项式,次数,记,n=deg(f(x),并称,a,n,为首项系数,首项系数为1多项式称为,首1多项式,.,第78页,2024/11/25 周一,78,多项式整环,记,Fx,为域上全部多项式,f(x),组成集合，则,Fx,关于通常多项式加法+和乘法 形成一个整环，叫,域,F,上（一元）多项式环,。0为其零元，1为其单位元。,在,Fx,上类似于整数环，关于多项式有商式、余式、整除、互素、最高公因式、最低公倍式等概念。,第79页,2024/11/25 周一,79,多项式带余除法,带余除法,：,a(x),b(x)Fx,且,b(x)0,则存在唯一,q(x),r(x)Fx,使,a(x)=q(x)b(x)+r(x),式中,deg(r(x)deg(b(x).,q(x),称为,商式,r(x),称为,余式,也用,a(x)mod p(x),表示,a(x),除以,p(x),余式.称为,a(x),模,p(x),，p(x),称为,模多项式,。,第80页,2024/11/25 周一,80,不可约多项式,若存在,q(x),b(x)，deg(q(x)1,deg(b(x)1，,使,a(x)=q(x)b(x)，,则称,a(x),为,可约多项式,，不然称为,不可约(既约)多项式,。,第81页,2024/11/25 周一,81,多项式运算,仅考虑一元多项式,可把多项式运算分为三种：,使用代数基本规则普通多项式运算；,系数运算是模,p,运算多项式运算，即系数在,Z,p,中；,系数在,Z,p,中，且多项式被定义为模一个多项式,m(x),多项式运算。,第82页,2024/11/25 周一,82,普通多项式运算,加法、减法为(相同次项)对应系数加减法,乘法为逐项相乘。,eg,let,f,(,x,)=,x,3,+,x,2,+2 and,g,(,x,)=,x,2,x,+1,f,(,x,)+,g,(,x,)=,x,3,+2,x,2,x,+3,f,(,x,),g,(,x,)=,x,3,+,x,+1,f,(,x,)x,g,(,x,)=,x,5,+3,x,2,2,x,+2,第83页,2024/11/25 周一,83,系数 在,Z,p,中多项式运算,在普通多项式运算中，全部系数都取,modp,运算。,尤其是,mod 2,多项式运算,ie all coefficients are 0 or 1,eg.let,f,(,x,)=,x,3,+,x,2,and,g,(,x,)=,x,2,+