信息数学课件--讲义

定义1设BA,是任意两个整数，其中0B。如果存在一个整数Q使得等式Q成立，就称整除A或者被B整除，记作|，并把叫做A的因数，把叫做的倍数。否则，就称不能整除或者不能被整除，记作|。由定义可知，0是任何非零整数的倍数；1是任何整数的因数；任何非零整数既是其自身的因数，又是其自身的倍数。由定义1及乘法运算的性质，立即可以得到整除关系具有下面性质性质1（）|BABA；（）CBC,|且；（）YXCTSA|,|有对任意的整数且；（）|且；（）设0C，则ABC|；（）若，则。（）若B，且,21KD是的全体因数，则/,/,21KD也是的全体因数。例1证明若N|3，|5，那么N|。；例2设BA,是两个非零整数，且存在整数TS,，使得TSA。证明（1）若M|,|，则有1；（2）若N，则有|。例3设A为奇数，B为偶数，且BA|，则2|。定义2设整数1,0N。如果除了因数1和N外，没有其他因数，则称为素数（或质数）。否则称其为合数。首先给出素数的一个判定定理。定理1设是一个大于1的正整数，如果对所有小于或等于N的素数P，都有N|，则一定是素数。由定理1，对于比较小的整数，我们可以迅速的判断出它是否为素数。例4求出所有不超过100的素数。算法111（1）2I（2）如果|，则不是素数，转到（7）；（3）如果I，则不是素数，转到（7）；（4）如果|5，则不是素数，转到（7）；（5）如果I，则不是素数，转到（7）；（6）输出的值；（7）1I（8）如果0，程序结束；（9）否则返回到（2）。输出的结果为235711131719232931374143475359616771737983899197从例4我们可以看出100以内的素数分布情况，进一步可以由上述例题求出10N以内的素数，这种求素数的方法称为爱拉托斯散（ERATOSTHENES）筛法。随着N的增加，按照上述方法判断出是否为素数的时间复杂度为21O。由定理1可以看出每个整数都有一个素因数，下面我们要证明每个整数一定可以表示成素数的乘积。定理2任一整数1N都可以表示成素数的乘积，即RPN1，RP2（1）其中I是素数。定理3素数有无穷多个。定理4形如K素数有无穷多个。上述两个定理都说明了一件事情素数有无穷多个。若以X表示不超过实数X的素数个数，记NP为第个素数，我们很容易得到的一个很弱的下界估计和的一个很弱的上界估计。定理5设全体素数按大小顺序排成的序列是,5,3,2541PP我们有XX2,LOG2，（2）和,1,12NPN（3）进一步运用简单的微积分知识我们可以得到更强一些的CHEBYSHEV不等式估计。定理6设实数2X。我们有NPNNL8L1，2XXL26L32事实上，还可以得到如下的极限形式X,1/LN，NP，这个结论也被称为素数定理。由素数定理可知，当X很大时，XL，表11说明了此种估计公式在越大时越准确。表11素数的分布XXXLN/X/LN3101681448116041229108571132595928685911046784987438241085710664579620420710718576145554286810106195084753448254942410541045505251243429448191048应用素数定理，我们可以分别估算出64位、128位的素数个数分别为176364052LNL274127128在64位奇数中任选一个奇数是素数的概率约为0/0563417在128位奇数中任选一个奇数是素数的概率约为0022，在256位奇数中任选一个奇数是素数的概率约为0011，即素数越大时，其分布越稀疏，因为数目越大时，比此数小的素数越多，则此数被整除的概率越大。素数的性质是数论的核心，也是现代密码学的一个重要内容，素数的分布情况和产生模型一直是人们研究的一个重要内容。几千年来，数学家对素数已有深入的研究。其中最有趣的一个问题是“是否有一个简单的方法或公式来产生素数”不幸的是，许多数学家的推测公式都是错误的，如1中国古代数学家曾提出下列测试法，以测试一个整数N是否为素数。若2|N，则为素数。事实上，对于所有小于341的素数，上述测试法都成立。2梅森素数形如1PM（为素数）的整数为素数者称为梅森（MERSENNE）素数。至今只发现27个，即497,230,17,94,68423,5317,2816501P是否有无穷个梅森素数还未证明。1不是素数。3费马素数形如2NNF（为自然数）的整数为素数者称为费马（FERMAT）素数。至今只发现5个费马素数尽管如此，迄今为止仍然没有发现素数的模型或产生素数的有效公式，因而寻找大的素数必须借助计算机一个一个地找。用计算机算两个512位（二进制）的素数的乘积是一件很容易的事情，但是如果给定一个1024位的数N，让你找出它是哪两个素数的乘积就困难多了，数学家至今还没有找到一种有效的方法去迅速分解一个合数。关于大合数因子分解的时间复杂度下限目前尚没有一般的结果，到现在为止的各种算法告诉人们这一时间下限将不低于LN2/1NEXPO，此结果明显比定理1给出的时间复杂度2/1低。因为不是任意两个整数都具有整除关系，所以我们引进带余数除法或欧几里得除法。定理7（欧几里得除法）设BA,是两个给定的整数，其中0B，则对任意的整数C，存在惟一的整数RQ,，使得RQA，|。称为除A的不完全商。在上式中取不同的C，就得到不同形式的带余数除法。（1）取0，则|BR，称R为A被B除后的最小非负余数，此时，可以看出，的充要条件是0；（2）取C，则|1，称为被除后的最小正余数，此时，可以看出，A的充要条件是|R；（3）取|B，则1|，称为A被B除后的最大非正余数，此时，可以看出，B|的充要条件是0R；（4）取|C，则0|R，称为被除后的最大负余数，此时，可以看出，AB|的充要条件是|BR；（5）当为偶数时，取2/|C，有2/|/|BR；取12/|C，有；当为奇数时，取/|，有/|1|/1|BR这时，称为绝对值最小余数。例5设7,6CB，则对任意一个整数A，A被除后的最小非负余数为被除后的最小正余数为被B除后的最大非正余数为A被除后的最大负余数为被除后的绝