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

1 离散数学 Discrete Mathematics 汪荣贵贵 教授 合肥工业业大学软软件学院专专用课课件 2010.04 Date 1 第二章第二章 算法基础算法基础 Date 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 递归 & 学习内容 Date 3 基础知识 中国余数定理 大整数的运算技巧 伪素数 密码学应用 &数论论的应应用 Date 4 定理1 若a和b为正整数，则存在整数 s和t，使gcd（a，b）=sa+tb & 基础知识 最大公因数的基本性质 Date 5 Date 6 引理1 如果a，b和c为正整数，使得gcd（a ，b）=1且a|bc，那么a|c Date 7 引理2 如果p是素数，且p|a1a2an，其中ai 为整数，则对于某个i，p|ai & 基础知识 由数学归纳法及引理1易证： Date 8 定理2 令m为整数，a，b和c为整数。如果 acbc（mod m）且gcd（c，m）=1，那么 ab（mod m）。 & 基础知识 Date 9 线性同余形为 axb（mod m） 的同余式. m为正整数，a和b为整数，x为变量 如果aa- 1(mod m), a- 称为a的模m逆 & 线性同余 Date 10 定理3 如果a和m为互素的整数， m1,则存在a的模m逆。而且这个a的 模m逆是唯一的。 （即有小于m的唯一正整数 a- ，它 是a的模m逆，且a的任何别的模m逆均 和a- 模m同余1） & 线性同余 Date 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逆 Date 12 例 求3模7的逆 解 由于gcd(3,7)=1, 由定理3知存在3模7的逆 7=23+1 -23+17=1 所以：-2是3模1的一个逆 & 线性同余 Date 13 给出一个在a和m互素的条 件下，求a的模m逆的方法： 求a和m的线性组合使之等 于1；这一线性组合中a的系数 就是a模m的一个逆 & 线性同余 Date 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 & 线性同余 Date 15 基础知识 中国余数定理 大整数的运算技巧 伪素数 密码学应用 &数论论的应应用 Date 16 定理4 令m1,m2,mn为两两互素的正整数 ，则同余方程组 x a1（mod m1） x a2（mod m2） x an（mod mn） 有唯一的模m=m1m2mn的解。（即有 一个解x，使0xm，且所有其他的解均 与次解模m同余） & 中国余数定理 Date 17 证明： 要构造一个适合各方程的解， 首先对k=1,2,n,令MK=m/mk,即Mk是除mk以 外所有模数的乘积。 由于ik时，mi和mk没有大于1的公因子， 所以gcd（mk，Mk）=1。 从而由定理3知有Mk模mk的逆，整数yk，使得 Mkyk=1（mod mk） 要得到合适所有方程的解，令 x a1M1y1+a2M2y2+anMnyn Date 18 现在证明x就是所求的一个解。 由于只要jk，就有 Mj=0（mod mk） x的计算式中除第k项以外的各项模mk均同余于0. 由于Mkyk 1（mod mk）， 我们看到，对k=1,2,n,均有 x akMkyk ak(mod mk) 所以，x是这n个同余方程的同一解。 & 中国余数定理 Date 19 例 一世纪时，中国数学家孙聪问道： 某物不知其数，三分之余二，五分之与 三，气分之余而，此物几何？这一问题可 以翻译成： 求同余方程组 x 2(mod 3) x 3(mod 5) x 2(mod 7) 的解 & 中国余数定理 Date 20 解 令m=357=105， M1=m/3=35,M2=m/5=21,M3=m/7=15. 2是M1=35的模3逆，因为352（mod 3） 1是M2=21的模5的逆，因为21 1(mod 5) 1也是M3=15的模7逆，因为15 1（mod 7） 于是这一方程组的解是那些满足下式的x： xa1M1y1+a2M2y2+a3M3y3=2352+3211+21 51 （mod 105）=233 23(mod 105) 23是所有解中最小正整数，被3除时余2，被5除时 余3，被7除时余2 Date 21 基础知识 中国余数定理 大整数的运算技巧 寻找伪素数 密码学应用 &数论论的应应用 Date 22 假定m1,m2,mn是大于或等于2且两两相 素的整数，令m为它们的乘积。 由中国余数定理可知每个整数a，0a m，均可用唯一的n元组表示。 这个n元组由a被mi除的余数组成，也就 是说，a可以唯一地表示为 （a mod m1,a mod m2,a mod mn） & 大整数的运算技巧 Date 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） & 大整数的运算技巧 Date 24 要做大整数算术运算，我们选模数 m1,m2,mn ，其中每个mi都是大于2的整 数，在ij时gcd（mi，mj）=1，且m= m1.m2 mn大于我们要做的算术运算的结果 大整数运算可以再表示它们的n元组的分量 上作运算来完成，n元组的分量是用大整数 除以mi的余数，i=1，2,n。一旦计算出 表示大整数算术运算结果的n元组表示，就 可以求解n个模mi同余方程（i=1，2,n ）找出结果的值。 & 大整数的运算技巧 Date 25 用该方法做大整数算术运算的优点： 首先可以用来完成通常一台计算机上不 能做的大整数算术运算。 其次，对不同模数的计算可以并行操 作，加快计算速度 & 大整数的运算技巧 Date 26 例 假定在某台处理器上做100以内的整数算术运 算比100以上的整数运算快得多，那么只要把整数表 示为模两两像素的100以内的整数的余数的多元组， 就可以将差不多所有整数计算限制在100以内的整数 上。例如，可以以99，98，97和95为模数。（这些整 数没有大于1的公因数） 根据中国余数定理，每个小于： 99989795=89 403 930 的非负整数均可唯一地用该整数被这四个因数除 的除数表示。 & 大整数的运算技巧 Date 27 例：计算机系统仅考虑100以内的数的处 理。如何对x=123684 和 y = 413456进 行相加运算？ 解的思路： 取四个两两互质的小于100的数99、98 、97、95，得到x+y的同余数表达。 再利用中国同余定理。 & 大整数的运算技巧 Date 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）表示的整数，必须解 同余方程组 Date 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是要求的 和。 & 大整数的运算技巧 Date 30 大整数算术运算模数的最好选 择是一组行为2k-1的整数，其中k 为正整数，这是因为很容易完成模 这种整数的二进制算术，还容易找 到两两互素的一组这种整数。 & 大整数的运算技巧 Date 31 基础知识 中国余数定理 大整数的运算技巧 伪素数 密码学应用 &数论论的应应用 Date 32 中国古代数学相信，n为素数的充分必要条件是2n -1 1（mod n） 当只要是素数该同余必成立，是正确的 只要同余成立，n就是素数，是不正确的 法国数学家费马证明了： 当n为素数时该同余成立 & 伪素数 Date 33 定理5（费马小定理) 如果p为一个 质数，a不能被p整除的整数，则有 ap-1 1 ( mod p) 并且对每个整数a，我们有 apa（mod p） & 伪素数 Date 34 通过编程计算发现，反过来结论并不成 立。例如， 但是341=11x34为合数！ 称使得 成立的p为伪素数。 Date 35 基础知识 中国余数定理 大整数的运算技巧 伪素数 密码学应用 &数论论的应应用 Date 36 信息，也就是字符串，被译 成数字，然后对每个字符对应的 数用移位或模26的线性同余转换 为另一个数。这些方法都是私钥 加密系统的例子。 & 密码学基本概念 Date 37 20世纪70年代中期，密码学中引入了公 钥密码系统的概念。 在这样的一个系统中，每个人都可以有 一个众所周知的加密密钥，而解密密钥是 保密的，只有信息的预期接受人能解密。 加密密钥并不能让人轻易找到解密密钥 & 密码学基本概念 Date 38 v用RSA加密法时，信息被翻译成若干整数 序列。为此可以先将每个字母翻译成整 数，例如用凯撒密码翻译。 v这些整数再分成组，各组成为一个大整 数，以代表一个字母段。 & RSA加密 Date 39 v加密过程是先把表示普通文字（即原信息 ）的整数M转换为表示密码文字（即加密信 息）的整数C，C的计算公式是 C=Memod n v 加密后的信息以一段段数字的形式发送给 预期的接收者 & RSA加密 Date 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=M13 mod 2537 Date 41 例 用RSA密码系统为信息STOP加密，其中p=43， q=59，所以n=4359=2537.此外e=13.注意 gcd（e，(p-1)(q-1)）=gcd(13,4258)=1 解（续） 为每一段加密。 快速取模乘法计算得 181913mod 2537=2081 141513mod 2537=2182 加密后的信息为 2081 2182 Date 42 v如果知道解密密钥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 & RSA解密 Date 43 由： C=Memodn 知： Cd =(Me)dmodn =Mdemodn =M1+k(p-q)(q-1) modn & RSA解密 Date 44 （假定gcd(M,p)=gcd(M,q)=1,这一关系只在很少 情况下不成立）， 根据费马小定理，有： Mp-1 1(mod p) 及 Mq-1 1(mod q) 于是 Cd M*(MP-1)k(q-1) M*1 M(mod p) 及 Cd M*(Mq-1)k(p-1) M*1 M(mod q) 由于gcd（p,q）=1,从中国余数定理知 Cd M(mod pq) Date 45 例 收到加密信息是0981 0461。如果这 是用上例中的RSA密码加密的，解密后 的原信息是什么？ 解 该信息是用RSA密码系统n=4359和 指数13加密的。 练习题4证明d=937是13模4258=2436 的逆数。我们用937作