补充1-基础数论.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,电子科技大学计算机科学与工程学院,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,*,Mr,*yr(mod M),Mi=M/mi,yi,=M,i-1,(mod m,i,)(1,i r),2.3,中国剩余定理,1.,中国剩余定理：,除数,余数,最小公倍数,衍数,乘率,各总,答数,m,1,b,1,m=m,1,m,2,m,k,M,1,M,1,M,1,M,1,b,1,X=,M,i,M,i,b,i,(mod m),m,2,b,2,M,2,M,2,M,2,M,2,b,2,m,k,b,k,M,k,M,k,M,k,M,k,b,k,其中：,m=,m,i,M,i,M,i,M,i,=1(mod m),Eg,:,求以下同余方程组的解：,x 5 mod 7,x 3 mod 11,x 10 mod 13,解：,r=3,m1=7,m2=11,m3=13;b1=5,b2=3,b3=10;,模,M=m1,m2,m3=1001,M1=M/m1=m2,m3 =143,M2=91,M3=77.,y1=M1,-1,(mod m1)=143,-1,(mod 7)=5,y2=4,y3=12.,解为,:x=b1,M1,y1+b2,M2,y2+b3,M3,y3 (mod M),=5,143,5,+3,91,4,+10,77,12,(mod 1001),=13907(mod 1001)=894,验证,:x=894=127,7+5=5,(mod 7),Eg,:“,今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”“答曰：二十三”（孙子算经）,问题等同于求以下同余方程组的解：,x 2 mod 3,x 3 mod 5,x 2 mod 7,解法：,除数,余数,最小公倍数,衍数,乘率,各总,答数,3,2,3x5x7=105,5x7,M,1,=2,35x2x2,140,63,30,233,5,3,7x3,M,2,=1,21x1x3,7,2,3x5,M,3,=1,15x1x2,2.4,模的幂运算,计算,X,a,(mod n),其中,x,a,n,Z,+,Eg,:,计算,2,1234,(mod 789),一种有效的方法：,2,4,16,2,8,256,2,16,256,2,49,2,32,49,2,34,2,64,34,2,367,2,128,367,2,559,2,256,559,2,37,2,512,37,2,580,2,1024,580,2,286,1234=1024+128+64+16+2,（,1234=(10011010010),2,）,2,1234,=286,559,367,49,4,481(mod 789),优势：,模的幂运算可快速完成，并且不需要太大内存,2.5,费马小定理和欧拉定理,1.Fermat,小定理,:,p,素数,a,是整数且不能被,p,整除,则,:a,p-1,1 mod p.,证明,:,考虑集合,s,1,=1,2,p-1,对每个数乘以,a,得到集合,s,2,=,a(modp),2a(modp),(p-1)a(modp),s2,中的元素两两不同且都在,1,与,p-1,之间,因此两个集合相同,于是,:(p-1)!=1,2,(p-1),a(modp,),2a(modp),(p-1)a(modp)mod p,a,2a,(p-1)a mod p,a,p-1,(p-1)!mod p,注意到,(p-1)!,与,p,互素,两边消去,(p-1)!,，得,a,p-1,1 mod p,eg,:,由,Fermat,小定理,:,2,10,=1024 1(mod 11),求,2,53,(mod 11)=?,2,53,=(2,10,),5,2,3,1,5,2,3,8(mod 11),通常情况下，如果,2,n-1,1(mod,n),n,为素数,然而,也有例外,:561=3,11 17,是合数,但,2,560,1(mod 561),因此，如果,2,n-1,1(mod n),那么,n,可能为素数。,但,2,n-1,模,n,不等于,1,那么,n,不可能为素数，这为我们提供一种寻找素数的方法，给定一个,n,计算,2,n-1,模,n,是否等于,1,，如果不等于,1,，,n,为非素数，如果等于,1,，还需用更复杂的方法来判断是否为素数，比如,(1),索洛维,-,斯特拉森,(,Solovay-Strassen,),素性检测算法,(2),米勒,-,罗宾,(Miller-Rabin),素性检测算法,(3)AKS,算法,2.,欧拉定理,.,(1),欧拉函数,(n,),是整数,1,a n,中满足,gcd(a,n,)=1,的个数,eg,:n=10,在,1,a n,中有四个,a,满足,gcd(a,n,)=1,，即,1,，,3,，,7,，,9,，所以,(n,)=4.,(a),定理,1,若,(m1,m2)=1,则,(m1m2),=,(m1)(m2),(b),定理,2,设,nZ,+,有分解式,n=p,1,e1,p,2,e2,.,p,m,em,其中,p,1,p,2,p,m,Z,+,是互不相同的素数,e1,e2,emZ,+,(n,)=n(1-1/p,1,)(1-1/p,2,)(1-1/p,m,),证明：,(n,)=(p,1,e1,),(p,2,e2,),(p,m,em,),下证：,(p,)=p,-p,-1,(p,),等于从,p,减去在,1,2,p,中与,p,不互素的数的个数，因为,p,是素数，故,(p,),等于从,p,减去在,1,2,p,中被,p,整除的数的个数。而在,1,2,p,p+1,2p,p,-1,p,中，,p,的倍数共有,p,-1,个，所以,(p,)=p,-,p,-1,(n,)=(p,1,e1,),(p,2,e2,),(p,m,em,),=(p,1,e1,p,1,e1-1,)(p,2,e2,-p,2,e2-1,)(p,m,em,-p,m,em-1,),=p,1,e1,p,2,e2,p,m,em,(1-1/p,1,)(1-1/p,2,)(1-1/p,m,),=n,(1-1/p,1,)(1-1/p,2,)(1-1/p,m,),(2),欧拉定理,如果,gcd(a,n,)=1,则,:,a,(n,),1mod n.,证明与费马小定理类似,.,注意：,n=p,时欧拉定理和费马小定理相同,eg,:,求,7,803,的后三位数字,解：,7,803,（,mod 1000,）的结果,(1000)=1000(1-1/2)(1-1/5)=400,，,有,7,803,(7,400,),2,7,3,343(mod 1000),eg,:,计算,2,43210,（,mod 101,）,解：,（,1,）由费尔马定理,2,100,（,mod 1001,）,1,（,mod 101,）,（,2,）,2,43210,(2,100,),432,2,10,2,10,1024(mod 101)=14,