信息数学课件--讲义.doc

此文档收集于网络，如有侵权，请联系网站删除定义1 设是任意两个整数，其中。 如果存在一个整数使得等式成立，就称整除或者被整除，记作，并把叫做的因数，把叫做的倍数。否则，就称不能整除或者不能被整除，记作。 由定义可知，0是任何非零整数的倍数；1是任何整数的因数；任何非零整数既是其自身的因数，又是其自身的倍数。由定义1及乘法运算的性质，立即可以得到整除关系具有下面性质性质1 （）；（）；（）；（）；（）设，则；（）若，则。（）若，且是的全体因数，则也是的全体因数。例1 证明：若，那么。；例2 设是两个非零整数，且存在整数，使得。证明（1）若，则有；（2）若，则有。例3 设为奇数，为偶数，且，则。定义2 设整数。如果除了因数和外，没有其他因数，则称为素数（或质数）。否则称其为合数。首先给出素数的一个判定定理。定理1 设是一个大于1的正整数，如果对所有小于或等于的素数，都有，则一定是素数。由定理1，对于比较小的整数，我们可以迅速的判断出它是否为素数。例4 求出所有不超过100的素数。算法1.1.1 （1） ;（2） 如果，则不是素数，转到（7）；（3） 如果，则不是素数，转到（7）；（4） 如果，则不是素数，转到（7）；（5） 如果，则不是素数，转到（7）；（6） 输出的值；（7） （8） 如果，程序结束； （9） 否则返回到（2）。输出的结果为2 3 5 7 11 13 17 1923 2931 3741 43 4753 5961 6771 73 7983 8991 97从例4我们可以看出100以内的素数分布情况，进一步可以由上述例题求出以内的素数，这种求素数的方法称为爱拉托斯散（Eratosthenes）筛法。随着的增加，按照上述方法判断出是否为素数的时间复杂度为。由定理1可以看出每个整数都有一个素因数，下面我们要证明每个整数一定可以表示成素数的乘积。定理2 任一整数都可以表示成素数的乘积，即， （1）其中是素数。定理3 素数有无穷多个。定理4 形如素数有无穷多个。上述两个定理都说明了一件事情：素数有无穷多个。若以表示不超过实数的素数个数，记为第个素数，我们很容易得到的一个很弱的下界估计和的一个很弱的上界估计。定理5 设全体素数按大小顺序排成的序列是：我们有， （2）和 （3）进一步运用简单的微积分知识我们可以得到更强一些的Chebyshev不等式估计。定理6 设实数。我们有， 事实上，还可以得到如下的极限形式，这个结论也被称为素数定理。由素数定理可知，当很大时，表1.1说明了此种估计公式在越大时越准确。表1.1 素数的分布168144.81.16012291085.7191.1047849874382.41.085664579620420.71.07157614555428681.01.0615084753448254942.41.054455052512434294481.91.048应用素数定理，我们可以分别估算出64位、128位的素数个数分别为在64位奇数中任选一个奇数是素数的概率约为在128位奇数中任选一个奇数是素数的概率约为0.022，在256位奇数中任选一个奇数是素数的概率约为0.011，即素数越大时，其分布越稀疏，因为数目越大时，比此数小的素数越多，则此数被整除的概率越大。素数的性质是数论的核心，也是现代密码学的一个重要内容，素数的分布情况和产生模型一直是人们研究的一个重要内容。几千年来，数学家对素数已有深入的研究。其中最有趣的一个问题是“是否有一个简单的方法或公式来产生素数？”不幸的是，许多数学家的推测公式都是错误的，如：1 中国古代数学家曾提出下列测试法，以测试一个整数是否为素数。若，则为素数。事实上，对于所有小于341的素数，上述测试法都成立。2梅森素数 形如（为素数）的整数为素数者称为梅森（Mersenne）素数。至今只发现27个，即是否有无穷个梅森素数还未证明。 不是素数。3费马素数 形如（为自然数）的整数为素数者称为费马（Fermat）素数。至今只发现5个费马素数尽管如此，迄今为止仍然没有发现素数的模型或产生素数的有效公式，因而寻找大的素数必须借助计算机一个一个地找。用计算机算两个512位（二进制）的素数的乘积是一件很容易的事情，但是如果给定一个1024位的数，让你找出它是哪两个素数的乘积就困难多了，数学家至今还没有找到一种有效的方法去迅速分解一个合数。关于大合数因子分解的时间复杂度下限目前尚没有一般的结果，到现在为止的各种算法告诉人们这一时间下限将不低于，此结果明显比定理1给出的时间复杂度低。因为不是任意两个整数都具有整除关系，所以我们引进带余数除法或欧几里得除法。定理7（欧几里得除法） 设是两个给定的整数，其中，则对任意的整数，存在惟一的整数，使得，。称为除的不完全商。在上式中取不同的，就得到不同形式的带余数除法。（1） 取，则，称为被除后的最小非负余数，此时，可以看出，的充要条件是；（2） 取，则，称为被除后的最小正余数，此时，可以看出，的充要条件是；（3） 取，则，称为被除后的最大非正余数，此时，可以看出，的充要条件是；（4） 取，则，称为被除后的最大负余数，此时，可以看出，的充要条件是；（5） 当为偶数时，取，有；取，有；当为奇数时，取，有这时，称为绝对值最小余数。例5 设，则对任意一个整数，被除后的最小非负余数为被除后的最小正余数为被除后的最大非正余数为被除后的最大负余数为被