5数论简介.pptVIP

a=572 57229 mod 713=113 加密 ab mod z = ((a mod z)(b mod z)) mod z 113 569 mod 713=572 解密 c=an mod z cs mod z 解密? RSA 密码系统第一次出现在1977 年2 月Martin Gardner 的Scientific American 专栏中，在这个专栏里，消息利用密钥z, n 加密，其中z 是64 位和65 位素数的乘积，n =9007，且悬赏$100 给首次破解这个密码的人。 在撰写这篇文章的时候，分解z 估计需要40 × 10005年。实际上，在1994 年5 月，Arjen Lenstra、Paul Leyland、Michael Graff 和Derek Atkins，在来自25 个国家的600 名志愿者的帮助下，利用超过1600 台的计算机分解了z。 本节复习 1. 密码学指的是什么？ 2. 什么是密码系统？ 3. 加密消息是什么意思？ 4. 解密消息是什么意思？ 5. 在RSA 公钥密码系统中，如何加密a，并传送给公钥z, n 的持有者？ 6. 在RSA 公钥密码系统中，如何解密c？ 7. RSA 公钥密码系统的安全依赖于什么？ 在十六进制中，用符号0、1、2、3、4、5、6、7、8、9、A、B、C、D、E 和F 来表示整数。符号A~F 相当于十进制中的10~15。 B4F = 11·162 + 4·161 + 15·160 现在来考虑相反的问题—把十进制数转换为以b 为基数的数。 例，把十进制数91 转换为二进制数。如果把91 除以2，可得到 91 = 2·45 + 1 45 = 2·22 + 1 例5.2.6 将十进制数130 转换成二进制数。 13010 = 100000102 算法5.2.7 转换成b为基数的整数 例5.2.9十进制转换成十六进制 将十进制数20385 转换为十六进制数 2038510 = 4FA116 任意基数的加法。 例5.2.13 十六进制加法 下面讨论计算an mod z 。 首先讨论计算幂an的算法。最直接的计算幂的办法是重复乘以a这需要n - 1 次乘法。优化：a29 = a1·a4·a8·a16 算法5.2.16 重复乘方计算指数 定理5.2.17 如果a、b 和z 是正整数， ab mod z = [(a mod z)(b mod z)] mod z 例5.2.18 计算57229 mod 713 为了计算a29，连续计算 a， a5 = a·a4, a13 = a5·a8, a29 = a13·a16 a2 mod z = [(a mod z)(a mod z)] mod z a4 mod z = a2a2 mod z = [(a2 mod z)(a2 mod z)] mod z a5 mod z = aa4 mod z = [(a mod z)( a4 mod z)] mod z a13 mod z = a5a8 mod z = [(a5 mod z)( a8 mod z)] mod z 计算 算法5.2.19 问题求解要点 将以b 为基数的数 cnbn + cn-1bn-1 +?+ c1b1 + c0b0 转换成十进制，用十进制执行每位的乘法和加法。 将十进制数n 转换成以b 为基数，用b 除，结果的商用b 除，结果的商接着用b 除，继续下去。这些余数给出了以b 为基数的n 的表示。第一个余数给出了第一个位的系数，下一个给出了第二个b 位的系数，如此下去。 5.3 欧几里得算法 寻找两个整数的最大公因子，欧几里得算法是一个古老、有名且有效的算法。 欧几里得算法是基于这个事实，如果 r = a mod b，那么 gcd (a, b) = gcd (b, r) gcd(105, 30) = gcd(30, 15) gcd(105, 30) = gcd(30, 15)  =gcd(15, 0) = 15 定理5.3.2 如果a 是一个非负整数，b 是一个正整数，r = a mod b，那么 gcd(a, b) = gcd(b, r) 算法5.3.3 欧几里得算法 例5.3.4 gcd(504, 396) a mod b = 504 mod 396 = 108 a mod b = 396 mod 108 = 72 a mod b = 108 mod 72 = 36 a mod b = 72 mod 36 = 0 a(36)，即396 和504 的最大公因子 定理5.3.6 如果0 到m（m ≥ 8）之间不同时为0 的一对整数作为