第2章 信息安全数学基础new(数论).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第,2,章 信息安全数学基础,2010,、,07,2026/1/30 周五,第,2,章 信息安全数学基础,2.4,模的幂运算,2.3,中国剩余定理,2.2,同余,2.1,基本概念,2.5,本 原 根,2026/1/30 周五,第,2,章 信息安全数学基础,2.1,基本概念,2026/1/30 周五,2.,整除的基本性质,(,N,整数集,),(1)a(a0),a|0,a|a(,同理,b,N,1|b),(2),b|a,cb|ca,(3),a|b,b|c,a|c,.,（传递性）,(4),a|b,a|c,a|(xb+yc,)(,x,yN,),(5),b|a,且,a0|,b|a,|,(6),cb|ca,b|a,1.,定义：,设整数,a,和,b,且,a,0,，如果存在整数,k,使得,b=,ak,，,那么就说,a,整除,b,（或,b,能被,a,整除）,，记作,a|b,，或者说,b,是,a,的倍数。,举例：,3|15,-15|60,整除定义及性质,2026/1/30 周五,带余数除法,：,如果,a,，,b,是两个整数，其中,b0,，则存在两个整数,q,和,r,，使得,a,bq,r,（,0r,b,）成立，且,q,和,r,是唯一的。,带余数除法,2026/1/30 周五,非负最小剩余的性质：,（,1,）,=+,（,2,）,=-,（,3,）,=,定义（非负最小剩余）,a,bq,r,（,0r,b,）中,r,叫做非负最小剩余，常记做,b,=r,（在不致引起混淆的情况下，,b,常常省略）,带余数除法,2026/1/30 周五,1.,定义：,一个大于1的整数,p,，,只能被,1,或者是它本身整除，而不能被其他整数整除，则称整数为素数,(prime number),，否则就叫做合数,(composite),。,eg,素数（,2,，,3,，,5,，,7,，,11,，,13,等）,合数（,4,，,6,，,8,，,9,，,12,等）,素数定义,及素数个数定理,2026/1/30 周五,2.,补充定理,(1),：设,a,是任一大于,1,的整数，则,a,的除,1,外的最小正因子,q,是素数，并且当,a,是合数时：,素数补充定理,2026/1/30 周五,2.,补充定理,(2),：,若,p,是一个素数，,a,是任一整数，则有,p|a,或,(p,，,a)=1,素数补充定理（续）,2026/1/30 周五,素数补充定理（续）,2.,补充定理：,p,为素数，且,p|ab,，那么,p|a,或,p|b,。,更一般地，如果,ab,z,能够被素数,p,整除，那么,a,b,z,中的某个数必能被,p,整除。,2026/1/30 周五,3.,素数个数定理（,1,）：素数的个数是无限的。,原因：,（,1,）,N,（,N1,）的除,1,外的最小正因数,q,是一个素数,（,2,）如果,q=p,i,，（,i,1,2,k),且,q|N,，因此,q|(N,-p,1,p,2,.,p,k,),，所以,q|1,，与,q,是素数矛盾。,素数个数定理及证明,证明：反证法,假设正整数个数是有限的，设为,p,1,p,2,.,p,k,令：,p,1,p,2,p,k,+1=N(N1),则,N,有一个素数,p,，且,pp,i,（,i=1,2,k).,故,p,是上述,k,个素数外的另外一个素数。,因此与假设矛盾。,2026/1/30 周五,素数定义及素数个数定理,3.,素数个数定理（,2,）：,设,(x),是小于,x,的素数个数，则,(x)x/,lnx,即,x,时，比值,(x)/(x/,lnx,)1,eg,:,可以估算,100,位素数的个数：,(10,100,)-,(10,99,)10,100,/(ln10,100,)10,99,/(ln10,99,),3.9*1097.,2026/1/30 周五,1.,整数的唯一分解定理定理（算术基本定理）,:,设,nZ,，有分解式，,n=p,1,e1,p,2,e2,.,p,m,em,，其中,p,1,p,2,p,m,Z,+,是互不相同的素数，,e1,e2,emZ,+,并且数对,(p,1,e1),(p,2,e2),(p,m,em,),由,n,唯一确定（即如果不考虑顺序，,n,的分解是唯一的）,.,eg,:504=2,3,3,2,7,1125=3,2,5,3,整数的唯一分解定理,2026/1/30 周五,1.,定义,两个整数,a,，,b,的最大公约数，就是能同时整除,a,和,b,的最大正整数，记为,gcd(a,b,),，或，,(,a,b,),。,eg,:gcd(5,7)=1,，,gcd(24,60)=12,，,最大公约数定义及求法,2.,求最大公约数的两种方法：,(1),因数分解：,eg,:1728=2,6,3,2,，,4536=2,3,3,4,7,gcd(1728,4536)=2,3,3,2,=72,。,2026/1/30 周五,(2),欧几里得,(Euclid),算法,设,a,b,N,ab0,用以下方法可求出,gcd(a,b,),。,最大公约数的欧几里得算法,2026/1/30 周五,Euclid,算法实例：求,gcd(132,108).,最大公约数的欧几里得算法（续）,2026/1/30 周五,欧几里得算法（例,1,）,gcd,（,1180,，,482,）,2,求：,gcd,（,1180,，,482,）,最大公约数的欧几里得算法（续）,2026/1/30 周五,欧几里得算法（例,2,）：求,gcd(12345,，,1111,),最大公约数的欧几里得算法（续）,2026/1/30 周五,欧几里得算法抽象,规律：余数除数被除数忽略,最大公约数的欧几里得算法（续）,2026/1/30 周五,欧几里得算法实现,最大公约数的欧几里得算法（续）,2026/1/30 周五,特别,a,b,为素数时,gcd(a,b,)=1,，存在,ma+nb,=1.,上述求,rn,=,ma+nb,的方法叫做,扩展的,Euclid,算法,利用该方法我们可以求,ax+by,=d,的解,这里,d=(,a,b,),证明：根据,Euclid,算法,a=bq,1,+r,1,b=r,1,q,2,+r,2,r,1,=r,2,q,3,+r,3,r,n-2,=r,n-1,q,n,+r,n,gcd(a,b,)=r,n,=r,n-2,-r,n-1,q,n,=,ma+nb,3.,定理,设,a,bZ,+,则存在,m,nZ,使得,gcd(a,b,)=,ma+nb,.,扩展的欧几里得算法,2026/1/30 周五,计算出了,gcd(a,b,);,但是并没有计算出两个数,m,，,n,来，使得：,ma+nb,=,gcd(a,b,),扩展的欧几里得算法,的结果,计算出了,gcd(a,b,);,计算出两个数,m,，,n,来，使得：,ma+nb,=,gcd(a,b,),扩展的欧几里得算法（续）,欧几里得算法,的结果,2026/1/30 周五,利用该方法我们可以求密码学方程,ax+by,=d,的解，这里,d=(,a,b,),例如,:,求,132x+108y=12,的解,解：,12=gcd(132,108),12=108-4,24,=108-4,(132-108,1),=108 4,132+4,108,=5*108 4*132,扩展的欧几里得算法（续）,2026/1/30 周五,第,2,章 信息安全数学基础,2.2,同 余,2026/1/30 周五,证明：,必要性,:,设,ab,(mod m),a=,mp+r,b=,mq+r,0rm,a-b=,m(p-q,),m|(a-b,).,充分性,:,设,m|(a-b,),a=,mp+r,b=,mq+s,0r,sm,a-b=,m(p-q)+(r-s,),m|(r-s,),0|r-s|1,，则,a,(n,),1(mod m),也就是说，如果,(a,m),1,，,m1,，则存在一个整数,满足,:,a,1(mod m),定义（整数的次数）：,若,(a,m),1,，,m1,，则使得同余式,a,1(mod m),成立的,最小正整数,叫做,a,对模,m,的,次数,。,2026/1/30 周五,整数的次数（续）,定理：设,a,对模数,m,的次数为,l,，,a,n,1,（,mod m,），则,l|n,。,证明：,如果结论不成立，则必有两个整数,q,和,r,，使得：,n,ql,r,（,0rl,）,而,1,a,n,a,(ql,r),a,ql,a,r,a,r,(mod m),，因此与,l,的定义相违背。,推论：设,a,对模数,m,的次数为,l,，则,l|,(m,),。,2026/1/30 周五,整数次数的计算：,因为,l|,(m,),，因此可以通过计算以下对模数,m,的值求出。,整数的次数（续）,例如：,m,7,，,a,2,(m),6,2,3,2,2,（,mod 7,）,4,2,3,（,mod 7,）,1,因此,a,对模数,m,的次数为,3,。,2026/1/30 周五,整数次数的有效计算方法（,1,）：,整数的次数（续）,2026/1/30 周五,整数次数的有效计算方法（,1,）：,整数的次数（续）,2026/1/30 周五,整数次数的有效计算方法（,2,）：,整数的次数（续）,2026/1/30 周五,整数的次数（续）,定理：设,a,对模数,m,的,次数,为,l,，,1,a,a,2,，,a,l,-1,对,模数,m,两两不同余。,证明：,如果结论不成立，则有某对,j,，,k,（,0jk,l,-1,，使得：,a,j,a,k,（,mod m,）,因此：,a,k-j,1,（,mod m,）,而,1,k-j,0,(g,m)=1,如果整数,g,对,m,的,次数,为,(m,),，则,g,叫做,m,的一个,本原根,（或,原根,）,.,eg,:3,是模,7,的,本原根,因为,3,(7),3,6,1(mod 7),本原根定义,2026/1/30 周五,本原根定义（续）,例如：,m,7,，,a,2,(m),6,2,3,2,2,（,mod 7,）,4,2,3,（,mod 7,）,1,因此：,a,对模数,m,的次数为,3,(m),所以：,2,不是,7,的本元根。,2,(,7,),mod 7=1,2026/1/30 周五,定理（原根）,设整数,m0,(g,m)=1,则,g,是,m,的一个原根的充要条件是：,g,，,g,2,，,g,(m,),组成模数,m,的一组缩系。,本原根判断,定理说明：如果,g,是,m,的一个原根，则模数,m,的一组缩系可表示为形如定理中的几何级数。,2026/1/30 周五,2.,定理：,设对素数,p,而言，如果,g,是一个,本原根,(1),如果,n,是,整数，那么,g,n,1(mod p),当且仅当,n,0(mod p-1),(2),如果,j,和,k,都是整数，那么,g,j,g,k,当且仅当,j,k(mod,p-1),本原根有关定理,2026/1/30 周五,问题：是否所有的正整数都有原根？,本原根有关定理（续）,例如：,m,12,(m),6,2,3,，与,m,互素的正整数包括,5,，,7,，,11,。,5,2,（,mod 12,）,1,因此，,5,对,12,的次数是,2,7,2,（,mod 12,）,1,因此,7,对模数,m,的次数为,2,11,2,（,mod 12,）,1,因此,11,对模数,m,的次数为,2,因此,m,12,没有原根。,2026/1/30 周五,定理（整数存在原根的必要条件）：,设,m1,，若,m,有原根，则,m,必为下列诸数之一：,2,，,4,，,p,l,，,2p,l,（,l,1,，,p,为奇素数）。,本原根有关定理（续）,定理（整数存在原根的充分条件）：,设,m,2,，,4,，,p,l,，,2p,l,（,l,1,，,p,为奇素数）时，则,m,有原根。,定理（整数原根个数）：,设,m,有一个原根,g,，则,m,恰有,(m,),个对模数,m,不同余的原根，这些原根由以下集合给出：,2026/1/30 周五,本原根有关定理（续）,2026/1/30 周五,原根的判断：,一般来说，判断,g,是否时一个素数,m,的原根时，不需要逐一计算,g,1,，,g,2,，,，,g,(m,),，而仅需要计算,g,t,(modm,），其中,t|(m,),。,本原根有关定理（续）,2026/1/30 周五,本原根有关定理（续）,2026/1/30 周五,本原根有关定理（续）,定理（原根的计算）：,2026/1/30 周五,本原根有关定理（续）,2026/1/30 周五,本原根有关定理（续）,2026/1/30 周五,本原根有关定理（续）,定理（原根的计算）：,2026/1/30 周五,本原根有关定理（续）,一个计算原根的算法：,2026/1/30 周五,本原根有关定理（续）,2026/1/30 周五,本原根有关定理（续）,2026/1/30 周五,指数,如果整数,m0,有一个元根,g,，,g,，,g,2,，,g,(m,),(,或数,1,g,，,g,，,g,2,，,g,(m)-1,）组成模数,m,的一组缩系。,例如，,3,是模,7,的,本原根，因此,：,3,1,3 3,2,2,3,3,6 3,4,4,3,5,5 3,6,1,上述六个数刚好是模数,m,的一组缩系。,2026/1/30 周五,指数（续）,定义：任一整数,n,，（,n,，,m,）,1,，必有唯一的整数,k,（,0k,（,m,），满足：,ng,k,（,mod m,）,其中,k,叫做,n,对模数,m,的指数，记做,k,ind,g,n,（简记为,ind,n,）,(,指数也叫做,离散对数,),。,2026/1/30 周五,指数（续）,2026/1/30 周五,指数（续）,2026/1/30 周五,指数（续）,2026/1/30 周五,指数的性质：设,g,是,m,的原根，如果,(,a,m,),(,b,m,),1,：,指数（续）,2026/1/30 周五,指数（续）,2026/1/30 周五,指数（续）,2026/1/30 周五,指数（续）,2026/1/30 周五,离散对数困难问题,基于离散对数困难性假设，,EIGamal,提出了,EIgamal,公钥密码体制。,2026/1/30 周五,离散对数困难问题（续）,2026/1/30 周五,课外阅读资料,Mao,Wenbo,，,Modern Cryptography:Theory and Practice,，电子工业出版社，,2004,2026/1/30 周五,Any Question?,Q&A,2026/1/30 周五,1,、利用扩展的欧几里德算法求,28mod75,的乘 法逆元,(a=75,b=28),。,2,、求,2,53,(mod 11)=?3,、解同余方程,5x,2,+6x+49=0(mod 60),。,4,、求,43,的所有原根。,5,、利用欧几里德算法求（,50,，,35,）的最大公约数。,6,计算,20,的欧拉函数。,2026/1/30 周五,