补充1-基础数论(精品)

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,电子科技大学计算机科学与工程学院,School of Computer Science And Technology,UESTC,2005,信息安全理论与技术,Introduction of Information Security Theory and Technology,第二章 基础数论,2.1,基本概念,2.2,同余,2.3,中国剩余定理,2.4,模的幂运算,2.5,费马小定理和欧拉定理,2.1,基本概念,1.,定义：,设整数,a,和,b,且,a,0,，如果存在整数,k,使得,b=,ak,，,那么就说,b,能被,a,整除,，记作,a|b,，或者说,b,是,a,的倍数。,举例：,3|15,-15|60,7 18,2.,整除的基本性质,N,整数集,(1)a(a0),a|0,a|a(,同理,b,N,1|b).,(2),a|b,b|c,a|c,.,（传递性）,(3),a|b,a|c,a|(xb+yc,)(,x,yN,).,2.1.1,整除,2.1,基本概念,带余数除法：,如果,a,，,b,是两个整数，其中,b0,，则存在两个整数,q,和,r,，使得,a,bq,r,（,0r,b,）成立，且,q,和,r,是唯一的。,证明：,（,1,）作一个整数序列,（,2,）反证法,2.1.1,整除,1.,定义：,一个大于1的整数,p,，,只能被,1,或者是它本身整除,而不能被其他整数整除，则称整数为素数,(prime number),，否则就叫做合数,(composite),。,eg,素数（,2,，,3,，,5,，,7,，,11,，,13,等）,合数（,4,，,6,，,8,，,9,，,12,等）,2.,素数个数定理（,1,）,：,设,(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.,2.1.2,素数,2.,素数个数定理（,2,）,：,素数的个数是无限的,证明：反证法,假设正整数个数是有限的，设为,p,1,p,2,.,p,k,令：,p,1,p,2,p,k,+1=N(N1),则,N,是一个素数（因为,N,不能被任何非,1,非,N,的因子整除），且,Np,i,（,i=1,2,k),。故,N,是上述,k,个素数外的另外一个素数。因此与假设矛盾。,2.1.2,素数,2.1.3,整数的唯一分解定理,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,的分解是唯一的）,.,3.,补充定理：,p,为素数，且,p|ab,那么,p|a,或,p|b,。,更一般地，如果,ab,z,能够被素数,p,整除，那么,a,b,z,中的某个数必能被,p,整除。,eg,:504=2,3,3,2,7,1125=3,2,5,3,2.1.4,最大公约数,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.,(2),欧几里德,(Euclid),算法,设,a,b,N,ab0,用以下方法可求出,gcd(a,b,).,Euclid,算法实例：求,gcd(132,108).,最大公约数,欧几里得算法（例,1,）,gcd,（,1180,，,482,）,2,求：,gcd,（,1180,，,482,）,最大公约数,欧几里得算法：求,gcd(12345,11111),12345=1,11111+1234,11111=9,1234+5,1234=246,5+4,5=1,4+1,4=4,1+0,gcd(12345,11111)=1,最大公约数,欧几里得算法抽象,规律：余数除数被除数忽略,最大公约数,欧几里得算法实现,3.,定理,设,a,bZ,+,则存在,m,nZ,使得,gcd(a,b,)=,ma+nb,.,证明：根据,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,特别,a,b,为素数时,gcd(a,b,)=1,，存在,ma+nb,=1.,上述求,rn,=,ma+nb,的方法叫做扩展的,Euclid,算法,利用该方法我们可以求,ax+by,=d,的解,这里,d=(,a,b,),欧几里得算法的结果,计算出了,gcd(a,b,);,但是并没有计算出两个数,m,，,n,来，使得：,ma+nb,=,gcd(a,b,),扩展的欧几里得算法的结果,计算出了,gcd(a,b,);,计算出两个数,m,，,n,来，使得：,ma+nb,=,gcd(a,b,),利用该方法我们可以求密码学概论,ax+by,=d,的解,这里,d=(,a,b,),eg,:,求,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,2.2,同余,1.,定义,设,a,bZ,mZ,+,如果,a,和,b,被,m,除所得余数相同，则称,a,和,b,关于模数,m,同余，记为,ab,(mod m).,2.,定理,设,a,bZ,mZ,+,则,ab,(mod m),m|(a-b,).,证明：,必要性,:,设,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|m,r=s,ab,(mod m).,证毕,3.,同余的性质,设,a,bZ,mZ,+,(1),自反性：,aZ,aa,(mod m).,(2),对称性：,ab,(mod m),ba,(mod m).,(3),传递性：,ab,，,bc,(mod m),ac,(mod m).,4.,模运算的性质,设,mZ,+,ab,(mod m),xy,(mod m),则有,(1),a+xb+y,(mod m),（加法）,(2)a-x,b-y,(mod m),（减法）,(3)ax by (mod m),（乘法）,4.,模运算的性质,（,4,）除法：相对复杂,如果：,12x,24,，那么：,3x,6,如果：,12x,24,（,mod3,），那么：,3x,6,（,mod3,）？,定理：设整数,a,，,b,，,c,，,n,（,n,0,），,gcd(a,，,n),1,，如果,ab,ac,（,mod n,），则,b,c,（,mod n,）。,例：,求解,2x,7 3,（,mod 17,）,解：,2x 3,7,（,mod17,）,2x,4,（,mod17,）,x,2,（,mod17,）,x 15,（,mod 17,）,计算成立的原因：,gcd,（,2,，,17,）,1,4.,模运算的性质,（,4,）除法：,例：,求解,5x,6,13,（,mod 11,）,解：,5x,13,6,5x,7,（,mod 11,）,x=7/5?,注意到,7,18,29,40,（,mod 11,）,所以：,5x,7,（,mod 11,）,5x,40,（,mod 11,）,x,8,（,mod 11,）,计算成立的原因：,gcd,（,5,，,11,）,1,5.,模,m,的乘法逆元,定义：设,mZ,+,x,yZ,如果,xy1(mod m),则称,y,是,x,的模,m,乘法逆元,记为,:y=x,-1,eg,：,2,31(mod 5),3,是,2,的模,5,乘法逆元,2,是,3,的模,5,乘法逆元,.,2,81(mod 5),8,是,2,的模,5,乘法逆元,.,注意：模,m,乘法逆元不唯一！,但是，如果求一个与模数互素的数的乘法逆元，则是唯一的。,扩展的欧几里得算法,欧几里得算法与乘法逆元,如果算法,gcd,（,a,，,b,）输出,r,m,1,，则,b,有乘法逆元,如果求出了,ma+nb,=1,中的整数,m,，,n,，则可以求出,b,（,mod a,）的乘法逆元。,因此欧几里得算法没有给出,b,的乘法逆元,b,1,如何求,b,1,？,扩展的欧几里得算法,乘法逆元与扩展的欧几里得算法,乘法逆元与扩展欧几里得算法,A,3,放大数,75,，,B,3,放小数,28,，,Q,放商。,A,1,，,A,2,初值为,1,0,，,B,1,，,B,2,初值为,0,1(,这是规定,).,算法开始。,当了,B,3,1,时，停止，这时的,B,2,就是乘法逆元。,28,1,mod75,867,例：求,28mod75,的乘法逆元,(a=75,b=28),商,Q,A,1,A,2,A,3,B,1,B,2,B,3,(,余数）,-,2,1,2,1,0,1,-1,0,1,-2,3,75,28,19,9,0,1,(=1-2*0),-1,3,1,-2,(=0-2*1),3,-8,28,19,(=75-2*28),9,1,扩展的欧几里得算法,6.,一次同余式,(1),定义,:,设,mZ,+,a,bZ,a0,我们把,ax+b0(mod m),称为模数,m,的一次同余式,.,如果,x,0,Z,满足,:,ax,0,+b0(mod m),则称,xx,0,(mod m),是同余式的解,.,eg,:,同余式,2x+1 0(mod 3),有解,x,0,=1.,同余式,2x+1 0(mod 4),无解,.,同余式,2x+1 0(mod 5),有解,x,0,=2.,(2),一次同余式的解,定理,1:,设,mZ,+,a,bZ,a0,(a,m)=1,则同余式,axb,(mod m),恰有一个解,xba,-1,(mod m).,eg,:,同余式,2x+10(mod 5),有解,:,x,0,=(-1)2,-1,42,3,322(mod 5),定理,2:,设,mZ,+,a,bZ,a0,(a,m)=d,则同余式,axb(mod,m),有解的充要条件是,d|b,.,在,d|b,的条件下,同余式有,d,个解,(,在模,m,的意义下,).,它们是,t+k,*,m/d,这里,k=0,1,2,.,d-1.,其中,t,是,(a/,d)x,(b/d)mod(,m/d,),的唯一解,.,eg,:,同余式,2x 3(mod 4),无解,d=(2,4)=2,3.,同余式,2x 4(mod 6),d=(2,6)=2|4,有,2,个解,:x=2,5.,求,154x 22(mod803),的解,.,则,(154,803)=11.,先求,(154/11)x 2mod(803/11).,即,14x 2(mod73),的解,.,解出,t 21(mod73),则,全体解为,:21,21+73,21+2*73,.,21+10*73.,2.3,中国剩余定理,1.,中国剩余定理,(,孙子,:Sun,Ze,公元前450年,孙子定理,),：,设自然数,m,1,m,2,m,r,两两互素，并记,M=m,1,m,2,m,r,，则同余方程组,:,x b1(mod m,1,),x b2(mod m,2,),.,.,x,br(mod,m,r,),有唯一解：,x b1*M1*y1+b2*M2*y2+,br