离散数学—newchap05.pptVIP

 第5章 数 论 简 介 数论是数学里研究整数的一个分支。传统上，由于它的抽象本质大于它的应用，因此将数论看做是数学的一个纯粹的分支。 英国数学家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。 例5.1.2 由于21 = 3·7，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。 定理5.1.3 令m、n 和d 是正整数。 如果d | m 且d | n， 那么d | (m + n)。 (b) 如果d | m 且d | n， 那么d | (m - n)。 (c) 如果d | m，那么d | mn。 定义5.1.4 对于一个大于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 是素数。 例5.1.6 序列 2, 3, 4, 5,..., 41, 42 中没有数可以整除43； 因此，43 是一个素数。 检查序列2, 3, 4, 5,..., 449, 450 中451 的可能的因子。 11 可以整除451（451 = 11·41）；因此，451 是一个合数。 定理5.1.7 一个大于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 年）发现了可以判断一个给定整数是否是素数的多项式时间算法。 是否存在一个分解整数的多项式时间算法，这个问题不仅仅有学术上的重要性，因为目前很多密码系统都依赖于不存在这样一个算法。 例5.1.10 如果一个合数n 输入到算法5.1.8 中，返回的因子是一个素数；也就是算法5.1.8 中返回一个合数的素数因子。 如果输入n = 1274 到算法5.1.8 中，算法返回素数2，因为素数2 整除1274，即1274 = 2·637 如果现在输入n = 637 到算法5.1.8 中，算法返回素数7，因为素数7 整除637，即637 = 7·91 如果现在输入n = 91 到算法5.1.8 中，算法返回素数7，因为素数7 整除91，即91 = 7·13 如果现在输入n = 13 到算法5.1.8 中，算法返回0，因为13 是素数。 把前面的过程组合起来得到1247 是素数的乘积： 1274 =