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

第二章 算法基础 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 递归 基础知识 中国余数定理 大整数的运算技巧 伪素数 密码学应用 定理1 若a和b为正整数，则存在整数s和t，使gcd（a，b）=sa+tb 引理1 如果a，b和c为正整数，使得gcd（a，b）=1且a|bc，那么a|c 引理2 如果p是素数，且p|a1a2…an，其中ai为整数，则对于某个i，p|ai 定理2 令m为整数，a，b和c为整数。如果ac≡bc（mod m）且gcd（c，m）=1，那么a≡b（mod m）。 线性同余形为 ax≡b（mod m） 的同余式. m为正整数，a和b为整数，x为变量 如果aa- ≡1(mod m), a- 称为a的模m逆 定理3 如果a和m为互素的整数，m1,则存在a的模m逆。而且这个a的模m逆是唯一的。 （即有小于m的唯一正整数 a- ，它是a的模m逆，且a的任何别的模m逆均和a- 模m同余1） 证： 由定理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逆 例 求3模7的逆 解 由于gcd(3,7)=1, 由定理3知存在3模7的逆 7=2×3+1 -2×3+1×7=1 所以：-2是3模1的一个逆 给出一个在a和m互素的条件下，求a的模m逆的方法： 求a和m的线性组合使之等于1；这一线性组合中a的系数就是a模m的一个逆 例 线性同余3x≡4(mod 7)的解是什么？ 解 从上例知道-2是3模7的逆。在同余式同乘以-2得： -2×3x=-2×4（mod 7） 因为-6≡1(mod 7)且-8 ≡6（mod 7）， 所以若x是解，必有x ≡-8 ≡6（mod 7）。 验证：3x ≡ 3×6=18 ≡4(mod 7) 6,13,20,…及-1，-8，-15 基础知识 中国余数定理 大整数的运算技巧 伪素数 密码学应用 定理4 令m1,m2,..,mn为两两互素的正整数，则同余方程组 x ≡a1（mod m1） x ≡a2（mod m2） x ≡an（mod mn） 有唯一的模m=m1m2…mn的解。（即有一个解x，使0≤xm，且所有其他的解均与次解模m同余） 证明： 要构造一个适合各方程的解， 首先对k=1,2,…,n,令MK=m/mk,即Mk是除mk以外所有模数的乘积。 由于i≠k时，mi和mk没有大于1的公因子，所以gcd（mk，Mk）=1。 从而由定理3知有Mk模mk的逆，整数yk，使得 Mkyk=1（mod mk） 要得到合适所有方程的解，令 x ≡a1M1y1+a2M2y2+…+anMnyn 现在证明x就是所求的一个解。 由于只要j≠k，就有 Mj=0（mod mk） x的计算式中除第k项以外的各项模mk均同余于0.由于Mkyk ≡1（mod mk）， 我们看到，对k=1,2,…,n,均有 x ≡ akMkyk ≡ak(mod mk) 所以，x是这n个同余方程的同一解。 例 一世纪时，中国数学家孙聪问道： 某物不知其数，三分之余二，五分之与三，气分之余而，此物几何？这一问题可以翻译成： 求同余方程组 x ≡2(mod 3) x ≡3(mod 5) x ≡2(mod 7) 的解 解 令m=3×5×7=105，M1=m/3=35,M2=m/5=21,M3=m/7=15. 2是M1=35的模3逆，因为35≡2（mod 3） 1是M2=21的模5的逆，因为21 ≡1(mod 5) 1也是M3=15的模7逆，因为15 ≡1（mod 7） 于是这一方程组的解是那些满足下式的x： x≡a1M1y1+a2M2y2+a3M3y3=2×35×2+3×21×1+2×15×1 （mod 105）=233 ≡23(mod 105) 23是所有解中最小正整数，被3除时余2，被5除时余3，被7除时余2 基础知识 中国余数定理 大整数的运算技巧 寻找伪素数 密码学应用 假定m1,m2,…,mn是大于或等于2且两两相素的整数，令m为它们的乘积。 由中国余数定理可知每个整数a，0≤a＜m，均可用