单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,1,离散数学,Discrete Mathematics,汪荣贵 教授,合肥工业大学软件学院专用课件,2010.04,11/19/2024,1,第二章 算法基础,11/19/2024,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,递归,学习内容,11/19/2024,3,基础知识,中国余数定理,大整数的运算技巧,伪素数,密码学应用,数论的应用,11/19/2024,4,定理1 若a和b为正整数，则存在整数s和t，使gcd（a，b）=sa+tb,基础知识,最大公因数的基本性质,11/19/2024,5,11/19/2024,6,引理,1,如果,a,，,b,和,c,为正整数，使得,gcd,（,a,，,b,）,=1,且,a|bc,，那么,a|c,11/19/2024,7,引理,2,如果,p,是素数，且,p|a,1,a,2,a,n,，其中,a,i,为整数，则对于某个,i,，,p|a,i,基础知识,由数学归纳法及引理1易证：,11/19/2024,8,定理,2,令,m,为整数，,a,，,b,和,c,为整数。如果,ac,bc,（,mod m,）且,gcd,（,c,，,m,）,=1,，那么,ab,（,mod m,）。,基础知识,11/19/2024,9,线性同余,形为,axb（mod m）,的同余式.,m为正整数，a和b为整数，x为变量,如果aa,-,1(mod m),a,-,称为a的模m逆,线性同余,11/19/2024,10,定理,3,如果,a,和,m,为互素的整数，,m1,则存在,a,的模,m,逆。而且这个,a,的模,m,逆是唯一的。,（即有小于,m,的唯一正整数,a,-,，它是,a,的模,m,逆，且,a,的任何别的模,m,逆均和,a,-,模,m,同余,1,）,线性同余,11/19/2024,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逆,11/19/2024,12,例,求3模7的逆,解,由于gcd(3,7)=1,由定理3知存在3模7的逆,7=23+1,-23+17=1,所以：-2是3模1的一个逆,线性同余,11/19/2024,13,给出一个,在a和m互素,的条件下，求a的模m逆的方法：,求a和m的,线性组合,使之等于1；这一线性组合中a的,系数,就是a模m的一个逆,线性同余,11/19/2024,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,线性同余,11/19/2024,15,基础知识,中国余数定理,大整数的运算技巧,伪素数,密码学应用,数论的应用,11/19/2024,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同余,）,中国余数定理,11/19/2024,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,11/19/2024,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个同余方程的同一解。,中国余数定理,11/19/2024,19,例,一世纪时，中国数学家孙聪问道：,某物不知其数，三分之余二，五分之与三，气分之余而，此物几何？这一问题可以翻译成：,求同余方程组,x 2(mod 3),x 3(mod 5),x 2(mod 7)的解,中国余数定理,11/19/2024,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,11/19/2024,21,基础知识,中国余数定理,大整数的运算技巧,寻找伪素数,密码学应用,数论的应用,11/19/2024,22,假定m,1,m,2,m,n,是大于或等于2且两两相素的整数，令m为它们的乘积。,由中国余数定理可知每个整数a，0,am，均可用唯一的n元组表示。,这个n元组由a被m,i,除的余数组成，也就是说，a可以唯一地表示为,（a mod m,1,a mod m,2,a mod m,n,）,大整数的运算技巧,11/19/2024,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）,大整数的运算技巧,11/19/2024,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）找出结果的值。,大整数的运算技巧,11/19/2024,25,用该方法做大整数算术运算的优点：,首先可以用来完成通常一台计算机上,不能,做的大整数算术运算。,其次，对不同模数的计算可以,并行,操作，加快计算速度,大整数的运算技巧,11/19/2024,26,例 假定在某台处理器上做100以内的整数算术运算比100以上的整数运算快得多，那么只要把整数表示为模两两像素的100以内的整数的余数的多元组，就可以将差不多所有整数计算限制在100以内的整数上。例如，可以以99，98，97和95为模数。（这些整数没有大于1的公因数）,根据中国余数定理，每个小于：,99,98,97,95=89 403 930,的非负整数均可唯一地用该整数被这四个因数除的除数表示。,大整数的运算技巧,11/19/2024,27,例,：计算机系统仅考虑100以内的数的处理。如何对x=123684 和 y=413456进行相加运算？,解的思路：,取四个两两互质的小于100的数99、98、97、95，得到x+y的同余数表达。,再利用中国同余定理。,大整数的运算技巧,11/19/2024,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）表示的整数，必须解同余方程组,11/19/2024,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是要求的和。,大整数的运算技巧,11/19/2024,30,大整数算术运算模数的最好选择是一组行为2,k,-1的整数，其中k为正整数，这是因为很容易完成模这种整数的二进制算术，还容易找到两两互素的一组这种整数。,大整数的运算技巧,11/19/2024,31,基础知识,中国余数定理,大整数的运算技巧,伪素数,密码学应用,数论的应用,11/19/2024,32,中国古代数学相信，n为素数的充分必要条件是2,n-1,1（mod n）,当只要是素数该同余必成立，是正确的,只要同余成立，n就是素数，是不正确的,法国数学家费马证明了：,当n为素数时该同余成立,伪素数,11/19/2024,33,定理5,（费马小定理)如果p为一个质数，a不能被p整除的整数，则有,a,p-1,1(mod p),并且对每个整数a，我们有,a,p,a（mod p）,伪素数,11/19/2024,34,通过编程计算发现，反过来结论并不成,立。例如，,但是,341=11x34为合数！,称使得,成立的p为伪素数。,11/19/2024,35,基础知识,中国余数定理,大整数的运算技巧,伪素数,密码学应用,数论的应用,11/19/2024,36,信息，也就是字符串，被译成数字，然后对每个字符对应的数用移位或模26的线性同余转换为另一个数。这些方法都是,私钥加密系统,的例子。,密码学基本概念,11/19/2024,37,20世纪70年代中期，密码学中引入了,公钥密码系统,的概念。,在这样的一个系统中，每个人都可以有一个众所周知的加密密钥，而解密密钥是保密的，只有信息的预期接受人能解密。,加密密钥并不能让人轻易找到解密密钥,密码学基本概念,11/19/2024,38,用,RSA,加密法时，信息被翻译成若干整数序列。为此可以先将每个字母翻译成整数，例如用凯撒密码翻译。,这些整数再分成组，各组成为一个大整数，以代表一个字母段。,RSA,加密,11/19/2024,39,加密过程是先把表示普通文字（即原信息）的整数,M,转换为表示密码文字（即加密信息）的整数,C,，,C,的计算公式是,C=,M,e,mod,n,加密后的信息以一段段数字的形式发送给预期的接收者,RSA,加密,11/19/2024,40,例,用RSA密码系统为信息STOP加密，,其中p=43，q=59，,所以n=4359=2537.,此外e=13.注意：,gcd（e，(p-1)(q-1)）=gcd(13,4258)=1,解,我们把STOP的字母翻