离散数学课件-第2章-5.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,1,离散数学,Discrete Mathematics,汪荣贵 教授,合肥工业大学软件学院专用课件,2010.04,2/1/2026,1,第二章 算法基础,2/1/2026,2,2.1 Algorithms,算法,2.2 Complexity of Algorithms,算法的复杂性,2.3 The Integers and Division,整数和除法,2.4 Integers and Algorithm,整数和算法,2.5 Applications of Number Theory,数论的应用,2.6 Matrices,矩阵,2.7,Recursion,递归,学习内容,基础知识,中国余数定理,大整数的运算技巧,伪素数,密码学应用,数论的应用,2/1/2026,4,定理,1,若,a,和,b,为正整数，则存在整数,s,和,t,，使,gcd,（,a,，,b,）,=,sa+tb,基础知识,最大公因数的基本性质,2/1/2026,5,2/1/2026,6,引理,1,如果,a,，,b,和,c,为正整数，使得,gcd,（,a,，,b,）,=1,且,a|bc,，那么,a|c,2/1/2026,7,引理,2,如果,p,是素数，且,p|a,1,a,2,a,n,，其中,a,i,为整数，则对于某个,i,，,p|a,i,基础知识,由数学归纳法及引理,1,易证：,2/1/2026,8,定理,2,令,m,为整数，,a,，,b,和,c,为整数。如果,ac,bc,（,mod m,）且,gcd,（,c,，,m,）,=1,，那么,ab,（,mod m,）。,基础知识,2/1/2026,9,线性同余,形为,axb,（,mod m,）,的同余式,.,m,为正整数，,a,和,b,为整数，,x,为变量,如果,aa,-,1(mod m),a,-,称为,a,的模,m,逆,线性同余,2/1/2026,10,定理,3,如果,a,和,m,为互素的整数，,m1,则存在,a,的模,m,逆。而且这个,a,的模,m,逆是唯一的。,（即有小于,m,的唯一正整数,a,-,，它是,a,的模,m,逆，且,a,的任何别的模,m,逆均和,a,-,模,m,同余,1,）,线性同余,2/1/2026,11,证：,由定理,1,及,gcd,（,a,，,m,）,=1,知有整数,s,和,t,，成立：,sa+tm,=1,于是,sa+tm,=1(mod m),由于,tm=0,（,mod m,）所以,sa,1,（,mod m,）,s,为,a,的模,m,逆,2/1/2026,12,例,求,3,模,7,的逆,解,由于,gcd(3,7)=1,由定理,3,知存在,3,模,7,的逆,7=23+1,-23+17=1,所以：,-2,是,3,模,1,的一个逆,线性同余,2/1/2026,13,给出一个,在,a,和,m,互素,的条件下，求,a,的模,m,逆的方法：,求,a,和,m,的,线性组合,使之等于,1,；这一线性组合中,a,的,系数,就是,a,模,m,的一个逆,线性同余,2/1/2026,14,例 线性同余,3x4(mod 7),的解是什么？,解 从上例知道,-2,是,3,模,7,的逆。在同余式同乘以,-2,得：,-23x=-24,（,mod 7,）,因为,-61(mod 7),且,-8 6,（,mod 7,），,所以若,x,是解，必有,x-8 6,（,mod 7,）。,验证：,3x 36=18 4(mod 7),6,13,20,及,-1,，,-8,，,-15,线性同余,2/1/2026,15,基础知识,中国余数定理,大整数的运算技巧,伪素数,密码学应用,数论的应用,2/1/2026,16,定理,4,令,m,1,m,2,.,m,n,为两两互素的正整数，则同余方程组,x a,1,（,mod m,1,）,x a,2,（,mod m,2,）,x a,n,（,mod,m,n,）,有唯一的模,m=m,1,m,2,m,n,的解。（即有一个解,x,，使,0 x,m,，且所有其他的解均与次解模,m,同余,）,中国余数定理,2/1/2026,17,证明：,要构造一个适合各方程的解，,首先对,k=1,2,n,令,M,K,=,m/m,k,即,M,k,是除,m,k,以外所有模数的乘积。,由于,ik,时，,m,i,和,m,k,没有大于,1,的公因子，所以,gcd,（,m,k,，,M,k,）,=1,。,从而由定理,3,知有,M,k,模,m,k,的逆，整数,y,k,，使得,M,k,y,k,=1,（,mod,m,k,）,要得到合适所有方程的解，令,x a,1,M,1,y,1,+a,2,M,2,y,2,+,a,n,M,n,y,n,2/1/2026,18,现在证明,x,就是所求的一个解。,由于只要,jk,，就有,M,j,=0,（,mod,m,k,）,x,的计算式中除第,k,项以外的各项模,m,k,均同余于,0.,由于,M,k,y,k,1,（,mod,m,k,），,我们看到，对,k=1,2,n,均有,x,a,k,M,k,y,k,a,k,(mod,m,k,),所以，,x,是这,n,个同余方程的同一解。,中国余数定理,2/1/2026,19,例,一世纪时，中国数学家孙聪问道：,某物不知其数，三分之余二，五分之与三，气分之余而，此物几何？这一问题可以翻译成：,求同余方程组,x 2(mod 3),x 3(mod 5),x 2(mod 7),的解,中国余数定理,2/1/2026,20,解,令,m=357=105,，,M,1,=m/3=35,M,2,=m/5=21,M,3,=m/7=15.,2,是,M,1,=35,的模,3,逆，因为,352,（,mod 3,）,1,是,M,2,=21,的模,5,的逆，因为,21 1(mod 5),1,也是,M,3,=15,的模,7,逆，因为,15 1,（,mod 7,）,于是这一方程组的解是那些满足下式的,x,：,xa,1,M,1,y,1,+a,2,M,2,y,2,+a,3,M,3,y,3,=2352+3211+2151,（,mod 105,）,=233 23(mod 105),23,是所有解中最小正整数，被,3,除时余,2,，被,5,除时余,3,，被,7,除时余,2,2/1/2026,21,基础知识,中国余数定理,大整数的运算技巧,寻找伪素数,密码学应用,数论的应用,2/1/2026,22,假定,m,1,m,2,m,n,是大于或等于,2,且两两相素的整数，令,m,为它们的乘积。,由中国余数定理可知每个整数,a,，,0,a,m,，均可用唯一的,n,元组表示。,这个,n,元组由,a,被,m,i,除的余数组成，也就是说，,a,可以唯一地表示为,（,a mod m,1,a mod m,2,a mod,m,n,）,大整数的运算技巧,2/1/2026,23,例,7,求表示小于,12,的非负整数的有序偶，其中第,1,分量是用,3,除的余数，第,2,分量是用,4,除以余数,解,：求出每个整数用,3,除和用,4,除的余数，得到：,0=,（,0,，,0,）,4=,（,1,，,0,）,8=,（,2,，,0,）,1=,（,1,，,1,）,5=,（,2,，,1,）,9=,（,0,，,1,）,2=,（,2,，,2,）,6=,（,0,，,2,）,10=,（,1,，,2,）,3=,（,0,，,3,）,7=,（,1,，,3,）,11=,（,2,，,3,）,大整数的运算技巧,2/1/2026,24,要做大整数算术运算，我们选模数,m,1,m,2,m,n,，其中每个,m,i,都是大于,2,的整数，在,ij,时,gcd,（,m,i,，,m,j,）,=1,，且,m=m,1,.m,2,m,n,大于我们要做的算术运算的结果,大整数运算可以再表示它们的,n,元组的分量上作运算来完成，,n,元组的分量是用大整数除以,m,i,的余数，,i=1,，,2,n,。一旦计算出表示大整数算术运算结果的,n,元组表示，就可以求解,n,个模,m,i,同余方程（,i=1,，,2,n,）找出结果的值。,大整数的运算技巧,2/1/2026,25,用该方法做大整数算术运算的优点：,首先可以用来完成通常一台计算机上,不能,做的大整数算术运算。,其次，对不同模数的计算可以,并行,操作，加快计算速度,大整数的运算技巧,2/1/2026,26,例 假定在某台处理器上做,100,以内的整数算术运算比,100,以上的整数运算快得多，那么只要把整数表示为模两两像素的,100,以内的整数的余数的多元组，就可以将差不多所有整数计算限制在,100,以内的整数上。例如，可以以,99,，,98,，,97,和,95,为模数。（这些整数没有大于,1,的公因数）,根据中国余数定理，每个小于：,99,98,97,95=89 403 930,的非负整数均可唯一地用该整数被这四个因数除的除数表示。,大整数的运算技巧,2/1/2026,27,例,：计算机系统仅考虑,100,以内的数的处理。如何对,x=123684,和,y=413456,进行相加运算？,解的思路：,取四个两两互质的小于,100,的数,99,、,98,、,97,、,95,，得到,x+y,的同余数表达。,再利用中国同余定理。,大整数的运算技巧,2/1/2026,28,解,123 684 mod 99=33 123 684 mod 98=8,，,123 684 mod 97=9,及,123 684mod95=89,123 684,表示为（,33,，,8,，,9,，,89,）,类似的,413 456,可表示为（,32,，,92,，,42,，,16,）,把,4,元组的对应分量相加，再按相应的模数减小各个分量。这样可得,（,33,，,8,，,9,，,89,）,+,（,32,，,92,，,42,，,16,）,=,（,65mod99,，,100mod98,，,51mod97,，,105mod95,）,=,（,65,，,2,，,51,，,10,）,求出（,65,，,2,，,51,，,10,）表示的整数，必须解同余方程组,2/1/2026,29,x,65,（,mod 99,）,x,2,（,mod 98,）,x,51,（,mod 97,）,x,10,（,mod 95,）,见练习,29,证明，,537 140,是方程组唯一小于,89 403 930,的非负解，因此,537 140,是要求的和。,大整数的运算技巧,2/1/2026,30,大整数算术运算模数的最好选择是一组行为,2,k,-1,的整数，其中,k,为正整数，这是因为很容易完成模这种整数的二进制算术，还容易找到两两互素的一组这种整数。,大整数的运算技巧,2/1/2026,31,基础知识,中国余数定理,大整数的运算技巧,伪素数,密码学应用,数论的应用,2/1/2026,32,中国古代数学相信，,n,为素数的充分必要条件是,2,n-1,1,（,mod n,）,当只要是素数该同余必成立，是正确的,只要同余成立，,n,就是素数，是不正确的,法国数学家费马证明了：,当,n,为素数时该同余成立,伪素数,2/1/2026,33,定理,5,（费马小定理,),如果,p,为一个质数，,a,不能被,p,整除的整数，则有,a,p-1,1(mod p),并且对每个整数,a,，我们有,a,p,a,（,mod p,）,伪素数,2/1/2026,34,通过编程计算发现，反过来结论并不成,立。例如，,但是,341=11x34,为合数！,称使得,成立的,p,为伪素数。,2/1/2026,35,基础知识,中国余数定理,大整数的运算技巧,伪素数,密码学应用,数论的应用,2/1/2026,36,信息，也就是字符串，被译成数字，然后对每个字符对应的数用移位或模,26,的线性同余转换为另一个数。这些方法都是,私钥加密系统,的例子。,密码学基本概念,2/1/2026,37,20,世纪,70,年代中期，密码学中引入了,公钥密码系统,的概念。,在这样的一个系统中，每个人都可以有一个众所周知的加密密钥，而解密密钥是保密的，只有信息的预期接受人能解密。,加密密钥并不能让人轻易找到解密密钥,密码学基本概念,2/1/2026,38,用,RSA,加密法时，信息被翻译成若干整数序列。为此可以先将每个字母翻译成整数，例如用凯撒密码翻译。,这些整数再分成组，各组成为一个大整数，以代表一个字母段。,RSA,加密,2/1/2026,39,加密过程是先把表示普通文字（即原信息）的整数,M,转换为表示密码文字（即加密信息）的整数,C,，,C,的计算公式是,C=,M,e,mod,n,加密后的信息以一段段数字的形式发送给预期的接收者,RSA,加密,2/1/2026,40,例,用,RSA,密码系统为信息,STOP,加密，,其中,p=43,，,q=59,，,所以,n=4359=2537.,此外,e=13.,注意：,gcd,（,e,，,(p-1)(q-1),）,=gcd(13,4258)=1,解,我们把,STOP,的字母翻译成相应的等价数码，然后按,4,个数字一组分段。这样得到,1819 1415,，用映射,C=M,13,mod 2537,2/1/2026,41,例,用,RSA,密码系统为信息,STOP,加密，其中,p=43,，,q=59,，所以,n=4359=2537.,此外,e=13.,注意,gcd,（,e,，,(p-1)(q-1),）,=gcd(13,4258)=1,解（续）,为每一段加密。,快速取模乘法计算得,1819,13,mod 2537=2081,1415,13,mod 2537=2182,加密后的信息为,2081 2182,2/1/2026,42,如果知道解密密钥,d,，即,e,模,(p-1)(q-1),的逆数，就可以很快恢复原信息。,（由于,gcd,（,e,(p-1)(q-1)=1,，该逆数一定存在。）,若,de1(mod(p-1)(q-1),则有整数,k,，成立,de=k(p-1)(q-1)+1,RSA,解密,2/1/2026,43,由：,C=,M,e,modn,知：,C,d,=(,M,e,),d,modn,=,M,de,modn,=M,1+k(p-q)(q-1),modn,RSA,解密,2/1/2026,44,（假定,gcd(M,p,)=,gcd(M,q,)=1,这一关系只在很少情况下不成立），,根据费马小定理，有：,M,p-1,1(mod p),及,M,q-1,1(mod q),于是,C,d,M*(M,P-1,),k(q-1),M*1,M(mod,p),及,C,d,M*(M,q-1,),k(p-1),M*1,M(mod,q),由于,gcd,（,p,q,）,=1,从中国余数定理知,C,d,M(mod,pq,),2/1/2026,45,例 收到加密信息是,0981 0461,。如果这是用上例中的,RSA,密码加密的，解密后的原信息是什么？,解,该信息是用,RSA,密码系统,n=4359,和指数,13,加密的。,练习题,4,证明,d=937,是,13,模,4258=2436,的逆数。我们用,937,作为解码指数。,要为数字段,C,解密，计算,P=C,937,mod 2537,2/1/2026,46,为解密上述信息，用,同余幂,算法计算,0981,937,mod2537=0704,及,0461,937,mod2537=1115.,从而原信息的数码形式是,0704 1115,。,翻译成字母,HELP,2/1/2026,47,如果知道模,n,的分解，即：,n=,pq,，则可以根据欧几里得算法迅速得到,e,模,(p-1)(q-1),的逆,d,。得以解密,但是，至今还没有有效的,n,的分解方法。,从目前的技术看：,分解,400,位的整数，需要十亿年！,RSA,系统的保密性,2/1/2026,48,本节内容到此结束,谢谢大家！,