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

《离散数学课件-第2章.ppt》由会员分享，可在线阅读，更多相关《离散数学课件-第2章.ppt（49页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、1离散数学Discrete Mathematics 2/20/20231第二章第二章 算法基础算法基础 2/20/202322.1 Algorithms2.1 Algorithms2.1 Algorithms2.1 Algorithms算法算法算法算法2.2 Complexity of Algorithms2.2 Complexity of Algorithms2.2 Complexity of Algorithms2.2 Complexity of Algorithms算法的复杂性算法的复杂性算法的复杂性算法的复杂性2.3 The Integers and Division2.3 The I

2、ntegers and Division2.3 The Integers and Division2.3 The Integers and Division整数和除法整数和除法整数和除法整数和除法2.4 Integers and Algorithm2.4 Integers and Algorithm2.4 Integers and Algorithm2.4 Integers and Algorithm整数和算法整数和算法整数和算法整数和算法2.5 Applications of Number Theory2.5 Applications of Number Theory2.5 Applicat

3、ions of Number Theory2.5 Applications of Number Theory数论的应用数论的应用数论的应用数论的应用2.6 Matrices2.6 Matrices2.6 Matrices2.6 Matrices矩阵矩阵矩阵矩阵2.7 2.7 2.7 2.7 RecursionRecursion 递归递归递归递归&学习内容学习内容2/20/20233基础知识中国余数定理大整数的运算技巧伪素数密码学应用&数数论的的应用用2/20/20234 定理1 若a和b为正整数，则存在整数s和t，使gcd（a，b）=sa+tb&基础知识基础知识最大公因数的基本性质最大公因数的

4、基本性质2/20/202352/20/20236引理引理1 1 如果如果a a，b b和和c c为正整数，使得为正整数，使得gcdgcd（a a，b b）=1=1且且a|bca|bc，那么，那么a|ca|c2/20/20237引理引理2 2 如果如果p p是素数，且是素数，且p|ap|a1 1a a2 2aan n，其中，其中a ai i为整数，则对于某个为整数，则对于某个i i，p|ap|ai i&基础知识基础知识由数学归纳法及引理由数学归纳法及引理1 1易证：易证：2/20/20238定理定理2 2 令令m m为整数，为整数，a a，b b和和c c为整数。如果为整数。如果acacbcbc

5、（mod mmod m）且）且gcdgcd（c c，m m）=1=1，那么，那么abab（mod mmod m）。）。&基础知识基础知识2/20/20239线性同余形为 axb（mod m）的同余式.m为正整数，a和b为整数，x为变量如果aa-1(mod m),a-称为a的模m逆&线性同余线性同余2/20/202310定理定理3 3 如果a和m为互素的整数，m1,则存在a的模m逆。而且这个a的模m逆是唯一的。（即有小于m的唯一正整数 a-，它是a的模m逆，且a的任何别的模m逆均和a-模m同余1）&线性同余线性同余2/20/202311证：由定理1及gcd（a，m）=1知有整数s和t，成立：sa

6、+tm=1于是 sa+tm=1(mod m)由于 tm=0（mod m）所以sa 1（mod m）s为a的模m逆2/20/202312例例 求3模7的逆解解 由于gcd(3,7)=1,由定理3知存在3模7的逆 7=23+1 -23+17=1所以：-2是3模1的一个逆&线性同余线性同余2/20/202313 给出一个给出一个在在a a和和m m互素互素的条的条件下，求件下，求a a的模的模m m逆的方法：逆的方法：求a和m的线性组合使之等于1；这一线性组合中a的系数就是a模m的一个逆&线性同余线性同余2/20/202314例 线性同余3x4(mod 7)的解是什么？解 从上例知道-2是3模7的逆

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/20/202315基础知识中国余数定理大整数的运算技巧伪素数密码学应用&数数论的的应用用2/20/202316定理4 令m1,m2,.,mn为两两互素的正整数，则同余方程组x a1（mod m1）x a2（mod m2）x an（mod mn）有唯一的模m=m1m2mn的解。（即有一个解x，使0 xm，且所有其他的解均与次解模m同余）&中国余数定理中国

8、余数定理2/20/202317证明：证明：要构造一个适合各方程的解，要构造一个适合各方程的解，首先对首先对k=1,2,n,k=1,2,n,令令M MK K=m/m=m/mk k,即即M Mk k是除是除m mk k以以外所有模数的乘积。外所有模数的乘积。由于由于ikik时，时，m mi i和和m mk k没有大于没有大于1 1的公因子，的公因子，所以所以gcdgcd（m mk k，M Mk k）=1=1。从而由定理从而由定理3 3知有知有M Mk k模模m mk k的逆，整数的逆，整数y yk k，使得，使得M Mk ky yk k=1=1（mod mmod mk k）要得到合适所有方程的解，

9、令要得到合适所有方程的解，令x ax a1 1M M1 1y y1 1+a+a2 2M M2 2y y2 2+a+an nM Mn ny yn n2/20/202318现在证明现在证明x x就是所求的一个解。就是所求的一个解。由于只要由于只要jkjk，就有，就有M Mj j=0=0（mod mmod mk k）x x的计算式中除第的计算式中除第k k项以外的各项模项以外的各项模m mk k均同余于均同余于0.0.由于由于M Mk ky yk k 1 1（mod mmod mk k），），我们看到，对我们看到，对k=1,2,n,k=1,2,n,均有均有x ax ak kM Mk ky yk k

10、a ak k(mod m(mod mk k)所以，所以，x x是这是这n n个同余方程的同一解。个同余方程的同一解。&中国余数定理中国余数定理2/20/202319例例 一世纪时，中国数学家孙聪问道：某物不知其数，三分之余二，五分之与三，气分之余而，此物几何？这一问题可以翻译成：求同余方程组 x 2(mod 3)x 3(mod 5)x 2(mod 7)的解&中国余数定理中国余数定理2/20/202320解解解解 令令m=357=105m=357=105，M M1 1=m/3=35,M=m/3=35,M2 2=m/5=21,M=m/5=21,M3 3=m/7=15.=m/7=15.2 2是是M

11、M1 1=35=35的模的模3 3逆，因为逆，因为352352（mod 3mod 3）1 1是是M M2 2=21=21的模的模5 5的逆，因为的逆，因为21 1(mod 5)21 1(mod 5)1 1也是也是M M3 3=15=15的模的模7 7逆，因为逆，因为15 115 1（mod 7mod 7）于是这一方程组的解是那些满足下式的于是这一方程组的解是那些满足下式的x x：xaxa1 1M M1 1y y1 1+a+a2 2M M2 2y y2 2+a+a3 3M M3 3y y3 3=2352+3211+2151=2352+3211+2151（mod 105mod 105）=233 2

12、3(mod 105)=233 23(mod 105)2323是所有解中最小正整数，被是所有解中最小正整数，被3 3除时余除时余2 2，被，被5 5除时除时余余3 3，被，被7 7除时余除时余2 22/20/202321基础知识中国余数定理大整数的运算技巧寻找伪素数密码学应用&数数论的的应用用2/20/202322 假定m1,m2,mn是大于或等于2且两两相素的整数，令m为它们的乘积。由中国余数定理可知每个整数a，0am，均可用唯一的n元组表示。这个n元组由a被mi除的余数组成，也就是说，a可以唯一地表示为（a mod m1,a mod m2,a mod mn）&大整数的运算技巧大整数的运算技巧

13、2/20/202323例例例例7 7 7 7 求表示小于求表示小于1212的非负整数的有序偶，其中第的非负整数的有序偶，其中第1 1分量是用分量是用3 3除的余数，第除的余数，第2 2分量是用分量是用4 4除以余数除以余数解解解解：求出每个整数用：求出每个整数用3 3除和用除和用4 4除的余数，得到：除的余数，得到：0=0=（0 0，0 0）4=4=（1 1，0 0）8=8=（2 2，0 0）1=1=（1 1，1 1）5=5=（2 2，1 1）9=9=（0 0，1 1）2=2=（2 2，2 2）6=6=（0 0，2 2）10=10=（1 1，2 2）3=3=（0 0，3 3）7=7=（1 1，

14、3 3）11=11=（2 2，3 3）&大整数的运算技巧大整数的运算技巧2/20/202324要做大整数算术运算，我们选模数要做大整数算术运算，我们选模数m m1 1,m,m2 2,m,mn n ，其中每个，其中每个m mi i都是大于都是大于2 2的整的整数，在数，在ijij时时gcdgcd（m mi i，m mj j）=1=1，且，且m=m=m m1 1.m.m2 2 m mn n大于我们要做的算术运算的结果大于我们要做的算术运算的结果元组的分量元组的分量n n大整数运算可以再表示它们的大整数运算可以再表示它们的元组的分量是用大整数元组的分量是用大整数n n上作运算来完成，上作运算来完成，

15、m m除以除以i i。一旦计算出。一旦计算出2,n2,n，i=1i=1的余数，的余数，元组表示，就元组表示，就n n表示大整数算术运算结果的表示大整数算术运算结果的m m个模个模n n可以求解可以求解i i，i=1i=1同余方程（同余方程（）找出结果的值。）找出结果的值。2,n2,n&大整数的运算技巧大整数的运算技巧2/20/202325用该方法做大整数算术运算的优点：用该方法做大整数算术运算的优点：首先可以用来完成通常一台计算机上首先可以用来完成通常一台计算机上首先可以用来完成通常一台计算机上首先可以用来完成通常一台计算机上不不不不能能能能做的大整数算术运算。做的大整数算术运算。做的大整数算

16、术运算。做的大整数算术运算。其次，对不同模数的计算可以其次，对不同模数的计算可以其次，对不同模数的计算可以其次，对不同模数的计算可以并行并行并行并行操操操操作，加快计算速度作，加快计算速度作，加快计算速度作，加快计算速度&大整数的运算技巧大整数的运算技巧2/20/202326 例例 假定在某台处理器上做假定在某台处理器上做100100以内的整数算术运以内的整数算术运算比算比100100以上的整数运算快得多，那么只要把整数表以上的整数运算快得多，那么只要把整数表示为模两两像素的示为模两两像素的100100以内的整数的余数的多元组，以内的整数的余数的多元组，就可以将差不多所有整数计算限制在就可以将

17、差不多所有整数计算限制在100100以内的整数以内的整数上。例如，可以以上。例如，可以以9999，9898，9797和和9595为模数。（这些整为模数。（这些整数没有大于数没有大于1 1的公因数）的公因数）根据中国余数定理，每个小于：根据中国余数定理，每个小于：99 99 9898 9797930930 403403 8989=9595 的非负整数均可唯一地用该整数被这四个因数除的非负整数均可唯一地用该整数被这四个因数除的除数表示。的除数表示。&大整数的运算技巧大整数的运算技巧2/20/202327例例：计算机系统仅考虑100以内的数的处理。如何对x=123684 和 y=413456进行相加

18、运算？解的思路：解的思路：取四个两两互质的小于100的数99、98、97、95，得到x+y的同余数表达。再利用中国同余定理。&大整数的运算技巧大整数的运算技巧2/20/202328解解 123 684 mod 99=33 123 684 mod 98=8 123 684 mod 99=33 123 684 mod 98=8，123 684 mod 97=9123 684 mod 97=9及及123 684mod95=89123 684mod95=89123 684123 684表示为（表示为（3333，8 8，9 9，8989）类似的类似的 413 456 413 456可表示为（可表示为（3

19、232，9292，4242，1616）把把4 4元组的对应分量相加，再按相应的模数减元组的对应分量相加，再按相应的模数减小各个分量。这样可得小各个分量。这样可得（3333，8 8，9 9，8989）+（3232，9292，4242，1616）=（65mod9965mod99，100mod98100mod98，51mod9751mod97，105mod95105mod95）=（6565，2 2，5151，1010）求出（求出（6565，2 2，5151，1010）表示的整数，必须解）表示的整数，必须解同余方程组同余方程组2/20/202329x x 6565（mod 99mod 99）x x 2

20、2（mod 98mod 98）x x 5151（mod 97mod 97）x x 1010（mod 95mod 95）见练习见练习2929证明，证明，537 140537 140是方程组唯一小于是方程组唯一小于89 89 403 930403 930的非负解，因此的非负解，因此537 140537 140是要求的是要求的和。和。&大整数的运算技巧大整数的运算技巧2/20/202330 大整数算术运算模数的最好选择是一组行为2k-1的整数，其中k为正整数，这是因为很容易完成模这种整数的二进制算术，还容易找到两两互素的一组这种整数。&大整数的运算技巧大整数的运算技巧2/20/202331基础知识中

21、国余数定理大整数的运算技巧伪素数密码学应用&数数论的的应用用2/20/202332中国古代数学相信，中国古代数学相信，n n为素数的充分必要条件是为素数的充分必要条件是2 2n-1n-1 11（mod nmod n）当只要是素数该同余必成立，是正确的当只要是素数该同余必成立，是正确的只要同余成立，只要同余成立，n n就是素数，是不正确的就是素数，是不正确的法国数学家费马证明了：法国数学家费马证明了：当当n n为素数时该同余成立为素数时该同余成立&伪素数伪素数2/20/202333定定理理5 5（费马小定理)如果p为一个质数，a不能被p整除的整数，则有 ap-1 1(mod p)并且对每个整数a

22、，我们有apa（mod p）&伪素数伪素数2/20/202334 通过编程计算发现，反过来结论并不成通过编程计算发现，反过来结论并不成立。例如，立。例如，但是但是341=11x34341=11x34为合数！为合数！称使得称使得成立的成立的p p为伪素数。为伪素数。2/20/202335基础知识中国余数定理大整数的运算技巧伪素数密码学应用&数数论的的应用用2/20/202336 信息，也就是字符串，被译信息，也就是字符串，被译成数字，然后对每个字符对应的成数字，然后对每个字符对应的数用移位或模数用移位或模2626的线性同余转换的线性同余转换为另一个数。这些方法都是为另一个数。这些方法都是私钥私钥

23、加密系统加密系统的例子。的例子。&密码学基本概念密码学基本概念2/20/202337 20世纪70年代中期，密码学中引入了公钥密码系统的概念。在这样的一个系统中，每个人都可以有一个众所周知的加密密钥，而解密密钥是保密的，只有信息的预期接受人能解密。加密密钥并不能让人轻易找到解密密钥&密码学基本概念密码学基本概念2/20/202338v用用RSARSA加密法时，信息被翻译成若干整数加密法时，信息被翻译成若干整数序列。为此可以先将每个字母翻译成整序列。为此可以先将每个字母翻译成整数，例如用凯撒密码翻译。数，例如用凯撒密码翻译。v这些整数再分成组，各组成为一个大整数，这些整数再分成组，各组成为一个大

24、整数，以代表一个字母段。以代表一个字母段。&RSARSA加密加密2/20/202339v加密过程是先把表示普通文字（即原信息）加密过程是先把表示普通文字（即原信息）的整数的整数M M转换为表示密码文字（即加密信息）转换为表示密码文字（即加密信息）的整数的整数C C，C C的计算公式是的计算公式是C=C=M Me emodmod n nv 加密后的信息以一段段数字的形式发送给加密后的信息以一段段数字的形式发送给预期的接收者预期的接收者&RSARSA加密加密2/20/202340例例例例 用用RSARSA密码系统为信息密码系统为信息STOPSTOP加密，加密，其中其中p=43p=43，q=59q=

25、59，所以所以n=4359=2537.n=4359=2537.此外此外e=13.e=13.注意：注意：gcd gcd（e e，(p-1)(q-1)(p-1)(q-1)）=gcd(13,4258)=1=gcd(13,4258)=1解解解解 我们把我们把STOPSTOP的字母翻译成相应的等价数的字母翻译成相应的等价数码，然后按码，然后按4 4个数字一组分段。这样得到个数字一组分段。这样得到 1819 14151819 1415，用映射，用映射C=MC=M1313 mod 2537 mod 25372/20/202341例例例例 用用RSARSA密码系统为信息密码系统为信息STOPSTOP加密，其中

26、加密，其中p=43p=43，q=59q=59，所以，所以n=4359=2537.n=4359=2537.此外此外e=13.e=13.注意注意 gcd gcd（e e，(p-1)(q-1)(p-1)(q-1)）=gcd(13,4258)=1=gcd(13,4258)=1解（续）解（续）解（续）解（续）为每一段加密。为每一段加密。快速取模乘法计算得快速取模乘法计算得181918191313mod 2537=2081mod 2537=2081141514151313mod 2537=2182mod 2537=2182 加密后的信息为加密后的信息为 2081 2182 2081 21822/20/20

27、2342v如果知道解密密钥d，即e模(p-1)(q-1)的逆数，就可以很快恢复原信息。（由于gcd（e,(p-1)(q-1)=1，该逆数一定存在。）v若de1(mod(p-1)(q-1)v则有整数k，成立de=k(p-1)(q-1)+1&RSARSA解密解密2/20/202343由：由：C=M C=Me emodnmodn知：Cd=(Me)dmodn =Mdemodn =M1+k(p-q)(q-1)modn&RSARSA解密解密2/20/202344 （假定（假定gcd(M,p)=gcd(M,q)=1,gcd(M,p)=gcd(M,q)=1,这一关系只在很少这一关系只在很少情况下不成立），情况

28、下不成立），根据费马小定理，有：根据费马小定理，有：M Mp-1p-1 1(mod p)1(mod p)及及M Mq-1q-1 1(mod q)1(mod q)于是于是C Cd d M*(M M*(MP-1P-1)k(q-1)k(q-1)M*1 M(mod p)M*1 M(mod p)及及C Cd d M*(M M*(Mq-1q-1)k(p-1)k(p-1)M*1 M(mod q)M*1 M(mod q)由于由于gcdgcd（p,qp,q）=1,=1,从中国余数定理知从中国余数定理知C Cd d M(mod pq)M(mod pq)2/20/202345例 收到加密信息是0981 0461。如

29、果这是用上例中的RSA密码加密的，解密后的原信息是什么？解 该信息是用RSA密码系统n=4359和指数13加密的。练习题4证明d=937是13模4258=2436的逆数。我们用937作为解码指数。要为数字段C解密，计算P=C937mod 25372/20/202346为解密上述信息，用为解密上述信息，用同余幂同余幂算法计算算法计算09810981937937mod2537=0704mod2537=0704及及04610461937937mod2537=1115.mod2537=1115.从而原信息的数码形式是从而原信息的数码形式是0704 11150704 1115。翻译成字母翻译成字母HELPHELP2/20/202347 如果知道模如果知道模n n的分解，即：的分解，即：n=pqn=pq，则可以根，则可以根据欧几里得算法迅速得到据欧几里得算法迅速得到e e模模(p-1)(q-1)(p-1)(q-1)的逆的逆d d。得以解密得以解密但是，至今还没有有效的但是，至今还没有有效的n n的分解方法。的分解方法。从目前的技术看：从目前的技术看：分解分解400400位的整数，需要十亿年！位的整数，需要十亿年！&RSARSA系统的保密性系统的保密性2/20/202348本节内容到此结束本节内容到此结束2/20/202349