离散数学-第19章.ppt

单击此处编辑母版标题样式,*,*,主要内容,素数,最大公约数与最小公倍数,同余,一次同余方程,欧拉定理与费马小定理,初等数论在计算机科学技术中的几个应用,第六部分 初等数论,1,第十九章 初等数论,主要内容,素数,最大公约数与最小公倍数,同余,一次同余方程,欧拉定理与费马小定理,初等数论在计算机科学技术中的几个应用,2,19.1,素数,今后只考虑正整数的正因子,.,平凡因子,:1,和自身,真因子,:,除,1,和自身之外的因子,例如,2,3,是,6,的真因子,设,a,b,是两个整数，且,b,0.,如果存在整数,c,使,a=,bc,，,则,称,a,被,b,整除,，或,b,整除,a,，,记作,b,|,a,.,此时,又称,a,是,b,的,倍数,，,b,是,a,的,因子,.,把,b,不整除,a,记作,b a,.,例如,6,有,8,个因子,1,2,3,和,6.,3,整除的性质,性质,19.1,若,a|b,且,a|c,则,x,y,有,a|,xb,+,yc,.,性质,19.2,若,a|b,且,b|c,则,a|c.,性质,19.3,设,m,0,则,a|b,当且仅当,ma|,mb,.,性质,19.4,若,a|b,且,b|a,则,a,=,b.,性质,19.5,若,a|b,且,b,0,则,|a|,|b|,.,带余除法,:,a=,qb+r,0,r,1,p,是素数且,d|p,则,d,=,p,.,性质,19.7,设,p,是素数且,p|,ab,则必有,p|a,或者,p|b,.,设,p,是素数且,p|a,1,a,2,a,k,则必存在,1,i,k,使得,p|,a,i,.,注意,:,当,d,不是素数时,d|,ab,不一定能推出,d|a,或,d|b,.,性质,19.8,a,1,是合数当且仅当,a,=,bc,其中,1,b,a,1,c,1,则,a,=,其中,p,1,p,2,p,k,是不相同的素数,r,1,r,2,r,k,是正整数,并且在不计顺序的情况下,该表示是惟一的,.,该表达式称作整数,a,的,素因子分解,.,例如,30=2,3,5,117=3,2,13,1024=2,10,推论,设,a=,其中,p,1,p,2,p,k,是不相同的素数,r,1,r,2,r,k,是正整数,则正整数,d,为,a,的因子的充分必要条件,是,d,=,其中,0,s,i,r,i,i,=1,2,k,.,6,例题,例,1,21560,有多少个正因子,?,解,21560=2,3,57,2,11,由推论,21560,的正因子的个数为,4232=48.,例,2,10!,的二进制表示中从最低位数起有多少个连续的,0?,解,2,3,4=2,2,5,6=23,7,8=2,3,9=3,2,10=25.,得,10!=2,8,3,4,5,2,7,故,10!,的二进制表示中从最低位数起有,8,个连续的,0.,7,素数的分布,梅森数,(Marin,Mersenne,):2,p,1,其中,p,为素数,当,n,是合数时,2,n,1,一定是合数,2,ab,1,=,(2,a,1)(2,a,(,b,1),+2,a,(,b,2),+2,a,+1).,梅森数可能是素数,也可能是合数,:2,2,1=3,2,3,1=7,2,5,1=31,2,7,1=127,都是素数,而,2,11,1=2047=2389,是合数,.,到,2002,年找到的最大梅森素数是,2,13466917,1,有,4,百万位,.,定理,19.2,有无穷多个素数,.,证 用反证法,.,假设只有有穷多个素数,设为,p,1,p,2,p,n,令,m=p,1,p,2,p,n,+1.,显然,p,i,m,1,i,n.,因此,要么,m,本身,是素数，要么存在大于,p,n,的素数整除,m,矛盾,.,8,素数的分布,(,续,),(,n,):,小于等于,n,的素数个数,.,例如,(0)=,(1)=0,(2)=1,(3)=,(4)=2,(5)=3.,168 1229 9592 78498 664579,145 1086 8686 72382 620421,1.159 1.132 1.104 1.085 1.071,(,n,),n,/ln,n,(,n,),n,/ln,n,10,3,10,4,10,5,10,6,10,7,n,定理,19.3,(,素数定理,),9,素数测试,定理,11.4,如果,a,是合数,则,a,必有小于等于 的真因子,.,证 由性质,19.8,a,=,bc,其中,1,b,a,1,c,(),2,=,a,矛盾,.,推论,如果,a,是合数,则,a,必有小于等于 的素因子,.,证 由定理,a,有小于等于 的真因子,b,.,如果,b,是素数,则结论成立,.,如果,b,是合数,由性质,19.9,和性质,19.5,b,有,素因子,p,b,.,根据性质,11.2,p,也是,a,的因子,结论也,成立,.,10,例,3,判断,157,和,161,是否是素数,.,解,都小于,13,小于,13,的素数有,:2,3,5,7,11.,检查结果如下,:,2 157,3 157,5 157,7 157,11 157,结论,:157,是素数,.,2 161,3 161,5 161,7|161,（,161=723,）,结论：,161,是合数,.,例题,11,1,2 3 4 5 6 7 8 9 10,1,2 3,4,5,6,7,8,9,10,1,2 3,4,5,6,7,8,9,10,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 35 36 37 38 39 40,41 42 43 44 45 46 47 48 49 50,51 52 53 54 55 56 57 58 59 60,61 62 63 64 65 66 67 68 69 70,71 72 73 74 75 76 77 78 79 80,81 82 83 84 85 86 87 88 89 90,91 92 93 94 95 96 97 98 99 100,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,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,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,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,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,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51 52,53,54,55,56 57 58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,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,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51 52,53,54 55 56 57 58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,埃拉托斯特尼,(,Eratosthene,),筛法,12,d,是,a,与,b,的,公因子,(,公约数,):,d,|,a,且,d,|,b,m,是,a,与,b,的,公倍数,:,a,|,m,且,b,|,m,定义,19.3,设,a,和,b,是两个不全为,0,的整数,称,a,与,b,的公因子中,最大的为,a,与,b,的,最大公因子,或,最大公约数,记作,gcd(,a,b,).,设,a,和,b,是两个非零整数,称,a,与,b,最小的正公倍数为,a,与,b,的,最小公倍数,记作,lcm(,a,b,).,例如,gcd(12,18)=6,lcm(12,18)=36.,对任意的正整数,a,gcd(0,a,)=,a,gcd(1,a,)=1,lcm(1,a,)=,a,.,19.2,最大公约数与最小公倍数,13,定理,19.5,(1),若,a|m,b|m,则,lcm(,a,b,)|,m,.,(2),若,d|a,d|b,则,d|,gcd(,a,b,).,证,(1),记,M,=lcm(,a,b,),设,m,=,qM,+,r,0,r,D,注意到,d,|,a,D|a,由,(1),得,m|a,.,同理,m|b,.,即,m,是,a,和,b,的公因子,与,D,是,a,和,b,的最大公约数矛盾,.,最大公约数与最小公倍数的性质,14,最大公约数与最小公倍数,(,续,),例,4,求,150,和,220,的最大公约数和最小公倍数,.,利用整数的素因子分解,求最大公约数和最小公倍数,.,设,其中,p,1,p,2,p,k,是不同的素数,r,1,r,2,r,k,s,1,s,2,s,k,是非负,整数,.,则,gcd(,a,b,)=,lcm(,a,b,)=,解,150=235,2,168=2,3,37.,gcd(150,168)=2,1,3,1,5,0,7,0,=6,lcm(150,168)=2,3,3,1,5,2,7,1,=4200.,15,辗转相除法,定理,19.6,设,a,=,qb,+,r,其中,a,b,q,r,都是整数,则,gcd(,a,b,)=,gcd(,b,r,).,证 只需证,a,与,b,和,b,与,r,有相同的公因子,.,设,d,是,a,与,b,的公因,子,即,d|a,且,d|b,.,注意到,r,=,a,qb,由性质,19.1,有,d|r,.,从而,d|b,且,d,|,r,即,d,也是,b,与,r,的公因子,.,反之一样,设,d,是,b,与,r,的公,因子,即,d,|,b,且,d|r,.,注意到,a,=,qb,+,r,故有,d|a,.,从而,d|a,且,d|b,即,d,也是,a,与,b,的公因子,.,16,辗转相除法,欧几里得,(Euclid),算法,辗转相除法,设整数,a,b,且,b,0,求,gcd(,a,b,).,做带余除法,a,=,qb,+,r,0,r,0,再对,b,和,r,做带余除法,b,=,q,r,+,r,0,r,0,是,a,和,b,的公因子,有,d|,xa,+,yb,即,d|,1.,从而,d,=1,得证,a,和,b,互素,.,定义,19.2,如果,gcd(,a,b,)=1,则称,a,和,b,互素,.,如果,a,1,a,2,a,n,中,的,任意两个都互素,则称它们,两两互素,.,例如,8,和,15,互素,而,8,和,12,不互素,.,4,9,11,35,两两互素,.,20,例题,例,6,设,a|c,b|c,且,a,与,b,互素,则,ab,|c,.,证 根据定理,19.8,存在整数,x,y,使,xa,+,yb,=1.,两边同乘以,c,得,cxa,+,cyb,=,c,.,又由,a|,xa,和,b|c,可得,ab,|,cxa,.,同理,ab,|,cyb,.,于是,有,ab,|,cxa,+,cyb,即,ab|c,.,21,19.3,同余,定义,19.3,设,m,是正整数,a,和,b,是整数,.,如果,m,|,a,b,则称,a,模,m,同余于,b,或,a,与,b,模,m,同余,记作,a,b,(mod,m,).,如果,a,与,b,模,m,不同余,则记作,a b,(mod,m,).,例如,153(mod 4),160(mod 4),14,2(mod 4),15 16(mod 4).,下述两条都是,a,与,b,模,m,同余的充分必要条件,:,(1),a,mod,m,=,b,mod,m,.,(2),a,=,b,+,km,其中,k,是整数,.,22,同余的性质,性质,19.10,同余关系是等价关系,即同余关系具有,自反性,.,a,a,(mod,m,),传递性,.,a,b,(mod,m,),b,c,(mod,m,),a,c,(mod,m,).,对称性,.,a,b,(mod,m,),b,a,(mod,m,).,缩写,a,1,a,2,a,k,(mod,m,).,性质,19.11,模算术运算,若,a,b,(mod,m,),c,d,(mod,m,),则,a,c,b,d,(mod,m,),ac,bd,(mod,m,),a,k,b,k,(mod,m,),其中,k,是非负整数,.,性质,19.12,设,d,1,d,|,m,则,a,b,(mod,m,),a,b,(mod,d,).,性质,19.13,设,d,1,则,a,b,(mod,m,),da,db,(mod,dm,).,性质,19.14,设,c,m,互素,则,a,b,(mod,m,),ca,cb,(mod,m,).,23,模,m,等价类,模,m,等价类,:,在模,m,同余关系下的等价类,.,a,m,简记作,a,.,Z,m,:Z,在模,m,同余关系下的商集,在,Z,m,上定义加法和乘法如下,:,a,b,a,+,b,=,a,+,b,a,b,=,ab,.,例,7,写出,Z,4,的全部元素以及,Z,4,上的加法表和乘法表,.,解,Z,4,=0,1,2,3,其中,i,=4,k,+,i,|,k,Z,i,=0,1,2,3.,0,1,2,3,0 1 2 3,+,0 1 2 3,1 2 3 0,2 3 0 1,3 0 1 2,0,1,2,3,0 1 2 3,0 0 0 0,0 1 2 3,0 2 0 2,0 3 2 1,24,例,8,3,455,的个位数是多少,?,解 设,3,455,的个位数为,x,则,3,455,x,(mod10).,由,3,4,1(mod 10),有,3,455,=3,4,113+3,3,3,7(mod 10),故,3,455,的个位数是,7.,例,9,日期的星期数,y,年,m,月,d,日星期数的计算公式,:,其中,M,=(,m,3)mod12+1,Y,=,y,M,/11,=100,C,+,X,Y,年,M,月,:3,月,下一年,2,月,C,:,Y,年的世纪数,),7,(mod,12,/,2,/,),7,/,(,2,2,4,/,4,/,d,m,M,M,M,C,C,X,X,w,+,+,+,+,+,-,+,+,例题,25,例题,例,9,(,续,),例如,中华人民共和国成立日,1949,年,10,月,1,日,C,=19,X,=49,M,=8,d,=1,是星期六,.,中国人民抗日战争胜利日,1945,年,8,月,15,日,C,=19,X,=45,M,=6,d,=15,是星期三,.,26,19.4,一次同余方程,定理,19.9,方程,ax,c,(mod,m,),有解的充要条件是,gcd(,a,m,)|,c,.,证 充分性,.,记,d,=,gcd(,a,m,),a,=,da,1,m,=,dm,1,c,=,dc,1,其中,a,1,与,m,1,互素,.,由定理,11.8,存在,x,1,和,y,1,使得,a,1,x,1,+,m,1,y,1,=1.,令,x,=,c,1,x,1,y,=,c,1,y,1,得,a,1,x,+,m,1,y,=,c,1,.,等式两边同乘,d,得,ax,+,my,=,c,.,所以,ax,c,(mod,m,).,必要性,.,设,x,是方程的解,则存在,y,使得,ax,+,my,=,c,.,由性质,19.1,有,d|c,.,一次同余方程,:,ax,c,(mod,m,),其中,m,0.,一次同余方程的,解,:,使方程成立的整数,例如,2,x,0(mod 4),的解为,x,0(mod 2),2,x,1(mod 4),无解,27,例题,例,10,解一次同余方程,6,x,3(mod 9).,解,gcd(6,9)=3|3,方程有解,.,取模,9,等价类的代表,x,=,4,3,2,1,0,1,2,3,4,检查它,们是否是方程的解,计算结果如下,:,6(,4)6(,1)623(mod 9),6(,3)60630(mod 9),6(,2)61646(mod 9),得方程的解,x,=,4,1,2(mod 9),方程的最小正整数解是,2.,28,模,m,逆,定理,19.10,(1),a,的模,m,逆存在的充要条件是,a,与,m,互素,.,(2),设,a,与,m,互素,则在模,m,下,a,的模,m,逆是惟一的,.,证,(1),这是定理,19.9,的直接推论,.,(2),设,ab,1,1(mod,m,),ab,2,1(mod,m,).,得,a,(,b,1,b,2,)0(mod,m,).,由,a,与,m,互素,b,1,b,2,0(mod,m,),得证,b,1,b,2,(mod,m,).,定义,19.4,如果,ab,1(mod,m,),则称,b,是,a,的,模,m,逆,记作,a,1,(mod,m,),或,a,1,.,a,1,(mod,m,),是方程,ax,1(mod,m,),的解,.,29,例题,例,11,求,5,的模,7,逆,.,解,5,与,7,互素,故,5,的模,7,逆存在,.,方法,1.,解方程,5,x,1(mod7).,检查,x,=,3,2,1,0,1,2,3,得到,5,1,3(mod7).,方法,2.,做辗转相除法,求得整数,b,k,使得,5,b,+7,k,=1,则,b,是,5,的模,7,逆,.,计算如下,:,7=5+2,5=22+1.,回代,1=5,22=5,2(7,5)=35,27,得,5,1,3(mod7).,方法,3.,直接观察,5,3=15,15,1(mod 7),得,5,1,3(mod7).,30,欧拉函数,(,n,):,0,1,n,1,中与,n,互素的数的个数,例如,(1)=,(2)=1,(3)=,(4)=2.,当,n,为素数时,(,n,)=,n,1;,当,n,为合数时,(,n,),n,1.,定理,19.11,(,欧拉定理,),设,a,与,n,互素,则,a,(,n,),1(mod,n,).,19.5,欧拉定理和费马小定理,31,欧拉定理的证明,证 设,r,1,r,2,r,(,n,),是,0,1,n,1,中与,n,互素的,(,n,),个数,.,由于,a,与,n,互素,对每一个,1,i,(,n,),ar,i,也与,n,互素,故存,在,1,(,i,),(,n,),使得,ar,i,r,(,i,),(mod,n,).,是,1,2,(,n,),上的映射,.,要证,是一个单射,.,a,的模,n,逆,a,1,存在,a,1,也与,n,互素,.,假设,i,j,(,i,)=,(,j,),则有,ar,i,ar,j,(mod,n,).,两边同乘,a,1,得,r,i,r,j,(mod,n,),矛盾,.,得证,是,1,2,(,n,),上的单射,当然也是,1,2,(,n,),上的,双射,.,从而,有,而 与,n,互素,故,a,(,n,),1(mod,n,).,32,费马,(Fermat),小定理,定理,19.12,(,费马小定理,),设,p,是素数,a,与,p,互素,则,a,p,-1,1(mod,p,).,另一种形式是,设,p,是素数,则对任意的整数,a,a,p,a,(mod,p,).,费马小定理提供了一种不用因子分解就能断定一个数是,合数的新途径,.,例如,2,9,1,4(mod 9),可以断定,9,是合数,.,33,19.6,初等数论在计算机科学技术中的几个应用,主要内容,产生均匀伪随机数的方法,密码学,34,产生均匀伪随机数的方法,随机数,:,随机变量的观察值,伪随机数,(0,1),上的均匀分布,U,(0,1):,a,(0,a,1),P,0,X,a,=,a,线性同余法,选择,4,个非负整数,:,模数,m,乘数,a,常数,c,和种子数,x,0,其中,2,a,m,0,c,m,0,x,0,m,用递推公式产生伪随机数序列,:,x,n,=(,ax,n,1,+,c,)mod,m,n,=1,2,取,u,n,=,x,n,/,m,n,=1,2,作为,U,(0,1),伪随机数,.,35,线性同余法与乘同余法,线性同余法产生的序列的质量取决于,m,a,和,c,.,例如,m,=8,a,=3,c,=1,x,0,=2,得到,7,6,3,2,7,6,周期为,4,m,=8,a,=5,c,=1,x,0,=2,得到,3,0,1,6,7,4,5,2,3,0,1,周期为,8.,a,=0,得到,c,c,c,a,=1,得到,x,0,+,c,x,0,+2,c,x,0,+3,c,乘同余法,:,c,=0(,x,0,0),的线性同余法,即,x,n,=,ax,n,1,mod,m,n,=1,2,.,最常用的均匀伪随机数发生器,:,m,=2,31,1,a,=7,5,的乘同余法,它的周期是,2,31,2.,36,密码学,恺撒,(Caesar),密码,加密方法,:ABCDEFGH I J KLMNOPQRS TUVWXYZ,DEFGH I JKLMNO PQRS TUVWXYZ ABC,明文,:SEE YOU TOMORROW,密文,:VHH BRX WRPRUURZ,18 4 4 24 14 20 19 14 12 14 17,17,14 22,21 7 7 1 17 23 22 17 15 17 20,20,17 25,加密算法,E,(,i,)=(,i,+,k,)mod 26,i,=0,1,25,解密算法,D,(,i,)=(,i,k,)mod,26,i,=0,1,25,其中,密钥,k,是一取定的整数,这里取,k,=3.,37,加密算法,线性同余加密算法,E,(,i,)=(,ai,+,b,)mod,26,i,=0,1,25,其中,a,与,26,互素,.,维吉利亚,(,Vigenere,),密码,把明文分成若干段,每一段有,n,个数字,密钥,k,=,k,1,k,2,k,n,加密算法,E,(,i,1,i,2,i,n,)=,c,1,c,2,c,n,其中,c,j,=(,i,j,+,k,j,)mod,26,i,j,=0,1,25,j,=1,2,n,.,38,RSA,公钥密码,私钥密码,:,加密密钥和解密密钥都必须严格保密,公钥密码,(W.Diffie,M.Hellman,1976):,加密密钥公开,解密密钥保密,RSA,公钥密码,(R.,Rivest,A.,Shamir,L.Adleeman,1978),取,2,个大素数,p,和,q,(,p,q,),记,n,=,pq,(,n,)=(,p,1)(,q,1).,选择正,整数,w,w,与,(,n,),互素,设,d,=,w,1,(mod,(,n,).,将明文数字化,分成若干段,每一个明文段,m,n,.,加密算法,c,=,E,(,m,)=,m,w,mod,n,解密算法,D,(,c,)=,c,d,mod,n,其中加密密钥,w,和,n,是公开的,而,p,q,(,n,),和,d,是保密的,.,39,解密算法正确性证明,要证,m,=,c,d,mod,n,即,c,d,m,(mod,n,),亦即,m,dw,m,(mod,n,).,由,dw,1(mod,(,n,),存在,k,使得,dw,=,k,(,n,)+1.,有两种可能,:,(1),m,与,n,互素,.,由欧拉定理,m,(,n,),1(mod,n,),得,m,dw,m,k,(,n,)+1,m,(mod,n,).,(2),m,与,n,不互素,.,不妨设,m,=,cp,且,q,不整除,m,.,由费马小定理,m,q,1,1(mod,q,).,于是,m,k,(,n,),m,k,(,p,1)(,q,1),1,k,(,p,1),1(mod,q,).,从而存在,h,使得,m,k,(,n,),=,hq,+1,两边同乘以,m,并注意到,m,=,cp,m,k,(,n,)+1,=,hcpq,+,m,=,hcn,+,m,得证,m,k,(,n,)+1,m,(mod,n,),即,m,dw,m,(mod,n,).,40,模幂乘运算,模幂乘运算,a,b,(mod,n,),设,b,=,b,0,+,b,1,2+,b,r,1,2,r,1,其中,b,i,=0,或,1,于是,令,A,0,=,a,A,i,(,A,i,1,),2,(mod,n,),i,=1,2,r,1,则有,41,例题,例,12,p,=43,q,=59,n,=4359=2537,(,n,)=4258=2436,w,=13.,A,B,Z,依次用,00,01,25,表示,各占,2,位,.,设明文段,m,=2106,即,VG,密文,c,=2106,13,mod 2537.,计算如下,:13=(1101),2,即,13=1+2,2,+2,3,.,A,0,=2106,431(mod 2537),A,1,(,431),2,560(mod 2537),A,2,560,2,988(mod 2537),A,3,(,988),2,601(mod 2537),2106,13,(,431)(,988)(,601)2321(mod 2537),得密文,c,=2321.,42,例题,(,续,),设密文,c,=0981.,d,=13,1,937(mod 2436),明文,m,=981,937,(mod 2537).,计算如下,:937=(1110101001),2,A,0,=981,A,1,981,2,838(mod 2537),A,2,838,2,505,A,3,(,505),2,1325,A,4,1325,2,21,A,5,21,2,441,A,6,441,2,868,A,7,(,868),2,65,A,8,(,65),2,849,A,9,(,849),2,293,981,937,9811325441(,65)(,849)293,704(mod 2537),得明文,m,=0704,即,HE.,43,第十九章 习题课,主要内容,素数与合数,埃拉托斯特尼筛法,最大公约数与最小公倍数,辗转相除法,同余,模,m,等价类及其运算,一次同余方程及有解的充分必要条件,欧拉定理与费马小定理,产生均匀伪随机数的方法,密码学,44,基本要求,熟练掌握整除、素数、合数的概念及其性质,掌握算术基本定理,能熟练地素因子分解,会判断素数,掌握埃拉托斯特尼筛法,.,熟练掌握最大公约数和最小公倍数的概念及其性质,会求最大公约数和最小公倍数,掌握辗转相除法,.,熟练掌握互素的概念及其性质,.,熟练掌握同余的概念及其性质,掌握一次同余方程的解存在的充分必要条件,掌握模,m,逆,的概念及存在的充分必要条件,会求一次同余方程的解和模,m,逆,.,掌握欧拉定理和费马小定理,.,45,要求,(,续,),会做不太难的证明,.,了解初等数论在伪随机数生成和密码学中的应用,掌握产生均匀伪随机数的线性同余法和乘同余法,知道明文、密文、加密、解密、密钥、私钥密码和公钥密码等概念，了解恺撒密码、维吉利亚密码和,RSA,公钥密码,.,46,练习,1,1.,判断下述命题是真是假,:,(1)3|-12;,(2)3|8;,(3)0|8;,(4)-21|0;,(5)527,465(mod 15);,(6)215,-175(mod 13).,T,T,T,F,F,F,47,2.,求,280,与,180,的最大公约数和最小公倍数,.,练习,2,解 方法一 利用整数的素因子分解,.,280=23,5,7,180=22,32,5.,gcd(280,180)=22,5=20,lcm(280,180)=23,32,5,7=2520.,方法二 用辗转相除法和公式,ab,=,gcd(,a,b,),lcm(,a,b,),280=180+100,180=100+80,100=80+20,80=4,20,得,gcd(280,180)=20,lcm(280,180)=280,180/20=2520.,48,3.,计算,:(1)2100mod 11;,练习,3,解 方法一 用带余除法,.,2100=190,11+10,得,2100mod 11=10.,方法二 利用同余的性质化简计算,.,2100,21,10,10,(-1),(-1),(-1),-1,10(mod 11),得,2100mod 11=10.,(2)2,340,mod 31.,解,2,340,2,5,68,32,68,1,68,1(mod 31),故,2,340,mod 31=1.,49,4.8,的模,3,逆是否存在,?,若存在,试给出,.,练习,4,解,8,与,3,互素,根据定理,19.10,8,的模,3,逆存在,.,方法一 直接观测,.,不难看出,2,8,1(mod 3),故,8,-1,(mod 3),2.,方法二 检查模,3,等价类的代表,0,1,2.,检查结果如下,:,0,8,0(mod 3),1,8,2(mod 3),2,8,1(mod 3),得,8,-1,2(mod 3).,方法三 用辗转相除法,.,计算如下,:,8=2,3+2,3=2+1,1=3-2=3-(8-2,3)=3,3-8,得,(-1),8,1(mod 3),8,-1,-1,2(mod 3).,50,5.,利用费马小定理证明,10,不是素数,.,练习,5,证,3,10-1,27,3,(-3),3,-27,3 1(mod 10),得证,10,不是素数,.,51,