离散数学-newcha.ppt

,离散数学,第5章 数 论 简 介,国外计算机科学教材序列离散数学(第6版)Richard Johnsonbaugh石纯一 等译 电子工业出版社,数论是数学里研究整数的一个分支。传统上，由于它的抽象本质大于它的应用，因此将数论看做是数学的一个纯粹的分支。英国数学家G.H.Hardy将数论看做是一个漂亮的、但不实用的数学分支。然而，在20 世纪后期，数论在密码系统（为了通信安全的系统）中得到了极大的应用。,内容,基本的数论定义，如“整除”和“素数”。因子分解、最大公因子和最小公倍数。整数的表示和一些整数算术的算法。用来计算最大公因子的欧几里得算法用于安全通信的RSA 系统。,5.1 因子,定义5.1.1 令n 和d 是整数，d 0。如果存在一个整数q 满足n=dq，称d 整除n。称q 是商，d是n 的一个因子或者约数。如果d 整除n，记做d|n。如果d 不能整除n，记做d|n。,由于21=37，3 整除21，记做3|21。商是7，称3 是21 的一个因子或者约数。注意到如果n 和d 是正整数，且d|n，那么d n。（如果d|n，那么存在一个整数q 使得n=dq。由于n 和d 是正整数，1 q。因此，d dq=n。）无论整数d 0 是否整除整数n，存在一个惟一的整数q（商）和r（余数）满足n=dq+r，0 r d）。余数r 等于0 当且仅当d可以整除n。,令m、n 和d 是正整数。如果d|m 且d|n，那么d|(m+n)。(b)如果d|m 且d|n，那么d|(m-n)。(c)如果d|m，那么d|mn。,对于一个大于1 的整数，它的因子只有其自身和1 被称为素数。一个大于1 的不是素数的整数称为合数。整数23 是一个素数，因为只有其本身和1 是它的因子。整数34 是合数因为它可以被17整除，17 既不是1 也不是34。,如果整数n 1是合数，那么它有一个正因子d 既不是1 也不是其自身。由于d 是正的且d 1，d 1。因为d 是n 的一个因子，d n。由于d n，d n。因此，判断一个正整数n 是否是合数，只需要试验一下整数2,3,.,n-1中的任何一个是否可以整除n。如果序列中存在某个整数能整除n，那么n 是合数。如果序列中没有整数可以整除n，那么n 是素数。,序列 2,3,4,5,.,41,42中没有数可以整除43；因此，43 是一个素数。检查序列2,3,4,5,.,449,450中451 的可能的因子。11 可以整除451（451=1141）；因此，451 是一个合数。,一个大于1 的正整数n 是合数当且仅当它有一个因子d，满足2 d。证明 必须证明如果n 是合数，那么n 有一个因子d，满足2 d，而且如果n 有一个因子d，满足2 d，那么n 是合数。,算法5.1.8 时间为(),判断一个整数是否是素数 这个算法判断一个整数n 1 是否是素数。如果n 是素数，算法返回0。如果n 是合数，算法返回一个因子d 满足2 d。为了判断d 是否整除n，算法检查n 被d 整除后余数n mod d 是否是0。,算法5.1.8 不是多项式时间的。,关于输入规模不是多项式时间的。目前还不知道是否存在一种多项式时间的算法，可以找到一个给定整数的因子；但是很多计算机科学家认为不存在这种算法。另一方面，Manindra Agarwal 与他的两个学生Nitin Saxena 和Neeraj Kayal，最近（2002 年）发现了可以判断一个给定整数是否是素数的多项式时间算法。是否存在一个分解整数的多项式时间算法，这个问题不仅仅有学术上的重要性，因为目前很多密码系统都依赖于不存在这样一个算法。,如果一个合数n 输入到算法5.1.8 中，返回的因子是一个素数；也就是算法5.1.8 中返回一个合数的素数因子。如果输入n=1274 到算法5.1.8 中，算法返回素数2，因为素数2 整除1274，即1274=2637如果现在输入n=637 到算法5.1.8 中，算法返回素数7，因为素数7 整除637，即637=791如果现在输入n=91 到算法5.1.8 中，算法返回素数7，因为素数7 整除91，即91=713如果现在输入n=13 到算法5.1.8 中，算法返回0，因为13 是素数。把前面的过程组合起来得到1247 是素数的乘积：1274=2637=2791=27713,任何一个大于1 的整数可以写成素数乘积的形式。此外，如果这些素数按非递减顺序写出，这种分解是惟一的。用符号表示，如果 n=p1p2pi 其中pk 是素数，p1 p2 pi，且 n=p1 ppj 其中pk 是素数，p1 p2 pj，那么 i=j，并且 pk=pk对所有的k=1,.,i,定理5.1.12 素数的个数是无限的。,证明 只要能够证明如果p 是素数，存在一个比p 大的素数就够了。为此，令 p1,p2,.,pn 代表所有比p 小或等于p 的不同素数。考虑整数 m=p1 p2pn+1 注意到m被pi 除时，余数是1：m=piq+1,q=p1 p2pi-1 pi+1pn 因此，对所有的i=1 到n，pi 不能整除m。令p 表示m 的一个素数因子（m 自身可以是也可以不是素数），那么p 不等于任何一个pi，i=1,2,.,n。由于p1,p2,.,pn 是所有比p 小或相等的素数，那么必须有p p。证明完成。,如何生成一个比11 大的素数。先列出所有小于或等于11 的素数 2,3,5,7,11 令 m=235711+1=2311 利用算法5.1.8，发现2311 是素数。现在已经找到了一个素数，就是2311。,最大公因子,两个整数m和n（不全为0）的最大公因子（greatest common divisor）是所有能够整除m 和n的最大正整数。例如，4 和6 的最大公因子是2，3 和8 的最大公因子是1。当检查分数m/n（其中m和n 是整数时）是否是最简的时，会用到最大公因子的概念。如果m和n 的最大公因子是1，m/n 是最简表示；否则，可以约减m/n。例如，4/6 不是最简表示，因为4 和6 的最大公因子是2，不是1。3/8 是最简表示，因为3 和8 的最大公因子是1。,令m和n 是整数，两者不同时为0。m 和n 的公因子是能够整除m和n 的整数。最大公因子记做 gcd(m,n)是m 和n 的最大的公因子。,30 的正因子是 1,2,3,5,6,10,15,30105 的正因子是 1,3,5,7,15,21,35,105所以30 和105 的正公因子是 1,3,5,15立刻可以得出30 和105 的公因子gcd(30,105)是15。,通过仔细观察30 和105 的素数因子来寻找它们的最大公因子：30=235 105=357,定理5.1.17,定义5.1.19 例5.1.20,令m 和n 是正整数。m 和n 的一个公倍数是一个可以同时被m 和n 整除的整数。最小公倍数，记做 lcm(m,n)是m 和n 的最小的正的公倍数30 和105 的最小公倍数lcm(30,105)是210，因为210 可以同时被30 和105 整除，并且经过试验，没有比210 小的整数可以同时被30 和105 整除。,可以通过观察30 和105 的素数因子，找到它们的最小公倍数 30=235 105=357lcm(30,105)的素数因子必须包含2、3 和5 作为因子（使得30 能整除lcm(30,105)）。同样，必须包含3、5 和7（使得105 能整除lcm(30,105)）。具有这个性质的最小数是 2357=210因此，lcm(30,105)=210。,对任意正整数m 和n，gcd(m,n)lcm(m,n)=mn证明 如果m=1，那么gcd(m,n)=1 且lcm(m,n)=n，因此 gcd(m,n)lcm(m,n)=1n=mn同样，如果n=1，那么gcd(m,n)=1 且lcm(m,n)=m，因此 gcd(m,n)lcm(m,n)=1m=mn假设m 1，n 1，将计算gcd 的公式（定理5.1.17）和lcm 的公式（定理5.1.22）组合起来，注意到 min(x,y)+max(x,y)=x+y,问题求解要点,判断一个整数n 1 是素数的最直接的办法是测试2,3,.,中任何一个是否能整除n。这个办法随着n 的增长太费时，因此只能用来判断相对比较小的n。本节给出了两个求a 和b 的最大公因子的方法。第一个方法是列出a 和b 的所有正因子，然后在所有公因子中，选择最大的。第二个方法是比较a 和b 的素数因子，如果pi 在a 中出现，p j 在b 中出现，那么pmin(i,j)在最大公因子的素数因子中。,5.2 整数的表示和整数算法,一个位（bit）是指一位二进制数字，即一个0 或一个1。计算机中，数据和指令都编码为位的形式。在计算机系统中，位在物理上如何表示依赖于所用技术。这一节讨论用位表示整数的二进位数制（二进制）和用16 个符号表示整数的十六进位数制。用8 个符号表示整数的八进位数制。,在十进制中，用10 个符号0、1、2、3、4、5、6、7、8 和9 表示整数。在表示整数时，符号的位置是有重要意义的：从右边开始，第一个符号表示1 的个数，下一个符号表示10 的个数，再下一个符号表示100 的个数，依次类推。例如，3854=3103+8102+5101+4100,在二进制（基数为2）中，为表示整数只需两个符号：0 和1。表示一个整数时，从右边开始，第一个符号表示1 的个数，下一个符号表示2 的个数，再下一个符号表示4 的个数，再下一个符号表示8 的个数，依次类推。例如，以2 为基数，,二进制数转换为十进制数 二进制数1011012 表示由1 个1，没有2、1 个4、1 个8、没有16 和1 个32 组成的数，可以表示为 1011012=125+024+123+122+021+120 用十进制计算等式的右边有 1011012=132+016+18+14+02+11=32+8+4+1=4510,将以b 为基数的整数转换成十进制 这个算法返回以b 为基数的整数cncn-1c1c0 的十进制值。,在十六进制中，用符号0、1、2、3、4、5、6、7、8、9、A、B、C、D、E 和F 来表示整数。符号AF 相当于十进制中的1015。B4F=11162+4161+15160,现在来考虑相反的问题把十进制数转换为以b 为基数的数。例，把十进制数91 转换为二进制数。如果把91 除以2，可得到 91=245+1 45=222+1,将十进制数130 转换成二进制数。13010=100000102,算法5.2.7 转换成b为基数的整数,例5.2.9十进制转换成十六进制,将十进制数20385 转换为十六进制数2038510=4FA116,任意基数的加法。,例5.2.13 十六进制加法,下面讨论计算an mod z。首先讨论计算幂an的算法。最直接的计算幂的办法是重复乘以a这需要n-1 次乘法。优化：a29=a1a4a8a16,算法5.2.16 重复乘方计算指数,如果a、b 和z 是正整数，ab mod z=(a mod z)(b mod z)mod z,计算57229 mod 713为了计算a29，连续计算 a，a5=aa4,a13=a5a8,a29=a13a16,a2 mod z=(a mod z)(a mod z)mod za4 mod z=a2a2 mod z=(a2 mod z)(a2 mod z)mod za5 mod z=aa4 mod z=(a mod z)(a4 mod z)mod za13 mod z=a5a8 mod z=(a5 mod z)(a8 mod z)mod z,计算,问题求解要点,将以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,如果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=108a mod b=396 mod 108=72a mod b=108 mod 72=36a mod b=72 mod 36=0a(36)，即396 和504 的最大公因子,欧几里得算法分析,当一对数a,b（a b）作为欧几里得算法的输入时，需要执行n 1 次模运算。那么a fn+2，且b fn+1，其中fn代表Fibonacci 序列。,如果0 到m（m 8）之间不同时为0 的一对整数作为欧几里得算法的输入，那么最多需要执行 次模运算。欧几里得算法最多需要执行33 次模运算就可以计算出从0 到1 000 000 之间不同时为0 的一个整数对的最大公因子。,如果a 和b 是非负整数，不同时为0，存在整数s 和t，使得 gcd(a,b)=sa+tb,假设有两个整数n 0，1，使得gcd(n,)=1。如何有效地计算一个整数s，其中 0 s，可以使ns mod=1。称s 是n mod 的逆。,5.4 RSA公用密码系统,密码学加密解密专用密码,专用密码,ABCDEFGHIJK LMNOPQRSTUVWXYZEIJFUAXVHWP GSRKOBTQYDMLZNC,SEND MONEYQARUESKRANSKRANEKRELINMONEY ON WAY,RSA 公用密码系统,公用加密密码私人解密密码01 02 A02 B,SEND MONEY,工作原理,选择一对素数 p qz=pq=(p-1)(q-1)选择满足 gcd(n,)=1 的n(一般为素数)计算满足 ns mod=1 的唯一的s(0s),open,open,保密,密码,公用密码 z n私用密码 s,加密解密过程,a,z,n,c=an mod z,s,a,cs mod z,原理,au mod z=a u mod=1cs mod z=(an mod z)s mod z=(an)s mod z=ans mod z=a,p=23 q=31 n=29 z=pq=713=(p-1)(q-1)=660s=569(29*569 mod 660=1)公用密码 29 713私用密码=569,a=57257229 mod 713=113 加密ab mod z=(a mod z)(b mod z)mod z113 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 公钥密码系统的安全依赖于什么？,