信息数学课件--讲义.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 19
23 29
31 37
41 43 47
53 59
61 67
71 73 79
83 89
91 97
从例4我们可以看出100以内的素数分布情况，进一步可以由上述例题求出以内的素数，这种求素数的方法称为爱拉托斯散（Eratosthenes）筛法。随着的增加，按照上述方法判断出是否为素数的时间复杂度为。
由定理1可以看出每个整数都有一个素因数，下面我们要证明每个整数一定可以表示成素数的乘积。
定理2 任一整数都可以表示成素数的乘积，即
， （1）
其中是素数。
定理3 素数有无穷多个。
定理4 形如素数有无穷多个。
上述两个定理都说明了一件事情：素数有无穷多个。若以表示不超过实数的素数个数，记为第个素数，我们很容易得到的一个很弱的下界估计和的一个很弱的上界估计。
定理5 设全体素数按大小顺序排成的序列是：

我们有
， （2）
和
（3）
进一步运用简单的微积分知识我们可以得到更强一些的Chebyshev不等式估计。
定理6 设实数。我们有
，

事实上，还可以得到如下的极限形式
，
，
这个结论也被称为素数定理。由素数定理可知，当很大时，，表1.1说明了此种估计公式在越大时越准确。
表1.1 素数的分布

168
144.8
1.160

1229
1085.7
1.132

9592
8685.9
1.104

78498
74382.4
1.085

664579
620420.7
1.071

5761455
5428681.0
1.061

50847534
48254942.4
1.054

455052512
434294481.9
1.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 设，则对任意一个整数，
被除后的最小非负余数为
被除后的最小正余数为
被除后的最大非正余数为
被除后的最大负余数为
被除后的绝对值最小余数为；
被除后的最小非负余数为
被除后的最小正余数为
被除后的最大非正余数为
被除后的最大负余数为
被除后的绝对值最小余数为
例6 证明：设是三个整数，则
（1）对任意的整数，必有；
（2）若，则；
（3）若，则；
（4）若，则。