网页登陆qq-糕点师

整数素性测试的研究
摘要：本文探索和研究了素性判定的理论方法，给出了朴素判
断 素数等六种素性测试方法，最后通过改进程序算法，与确定性素
性测试方法进行比较，取得了较为理想的 结果。
关键词：素性测试 概率算法 c-free
1.素数的概述
根据素数的 定义，因数只有1和它本身的整数叫为素数。一个
基本问题是如何有效地确定一个数是否是一个素数，即 素性测试问
题。最简单的办法就是直接利用素数的定义来判断。但对于大素数
来说，由于计算量 太大，根本无法实现用于具体的应用系统中。故
需要根据素数判断的理论研究新的程序算法，以此来提高 素数判断
的效率。
2.素性判定的方法
①朴素判断素数。根据素数的定义，假设一 个整数为n，从2到
n-1的整数都枚举一遍，判断是否存在能整除n的整数，如果都不
能则n 为素数。
容易发现，用这种方法判断整数n是否为素数需要n-2次判断。
在n非常大或者测 试量很大时，这种方法显然不可取。
②改进朴素判断素数。对于一个小于n的整数x，如果n不能整< br>除x，则n必然不能整除nx。反之相同。所以按照素数定义来判
断素数时，可以进行一个较为明 显的优化。即我们只需从2枚举到 。
因为在判断2的同时也判断了n2，……，以此类推，到 时，把2

到n-1的数都判断过了，对于一个整数n，需要测试 次。
③标准的爱拉托逊斯筛选法。具 体做法是：先把n个自然数按
次序排列起来。1不是质数也不是合数，划去。第二个数2是质数
留下来，而把2后面所有能被2整除的数都划去。2后面第一个没
划去的数是3，把3留下，再把3后面 所有能被3整除的数都划去。
这样一直做下去，就会把不超过n的全部合数都筛掉，留下的就是
不超过n的全部质数。
④朴素判断+筛法。由 ③可知，用筛法直接判断素数是很有限
的，当 很大时，显然不可取。故将朴素判断和筛法结合在一起，
能使朴素判断得到进一步优化。用筛法预处理出 小于 的所有素数，
这样在大量数据测试的时候效率提高很多。
⑤费马素性测试。费马测试的 具体实现是，对于n，从素数表中
取出任意的素数对其进行费马测试，如果取了很多个素数，n仍未测试失败，那么则认为n是素数。
⑥米勒-拉宾素性测试。拉宾米勒测试是一个不确定的算法，只
能从概率意义上判定一个数可能是素数，但并不能确保。
设n为奇素数，存在q，m使得n-1=2qm，（q≥1）。序列
的最后一项为an-1（modn）， 且每一项是前面一项的平方。对
于任意i（i=0，1，…q-1）， 判断a2im（modn）是否为1和n-1，
且它的后一项是否为1。
如果其后项为1，但本项不等于1和n-1， 则它就是非平凡的
根，从而知道n不是素数。

3.素性判定的改进及结果分析
通过以上六种方法的分析，能更清晰更具体地看到素数判断在
不同的需求下会有不同的算法选择。在已经较全面地介绍素性检测
算法的基础上，这里又着重研 究改进了米勒-拉宾算法，这也是一
类概率性的素数检测方法，当输出结果为“prime”时，仅以一 定
的高概率保证被检测数的素性。不过概率性检测一般要比确定性检
测快得多。
设计的算法是在c-free环境下实现的，在更短的时间内判定大
整数是否为素数，即： < br>在整数位数较少、整数数目不多的情况下，用该算法不能明显
体现其优越性，因此随机取出100 个16-18位大整数，在同一批数
据的情况下，对于这个概率性算法与确定性算法，比较跑完所用的< br>时间以及检测的正确性。
随机给出100组整数，用概率性算法和确定性算法测试，下面
是两者在c- free环境中运行后的部分结果：
经多次试验，增加整数位数和整数数量（即大整数），两种算法< br>所需时间都增加了，但在大整数前提下，显然新概率性算法跑完的
时间远小于传统的确定性算法， 这样就能大幅度提高素性测试的效
率。而且在测试这100个整数时，最后发现两组结果一样。
确定性算法对于素性判定的正确率很高，但随着整数的变大，
其运行速度随之也减慢。而在改进的概率 性程序算法中，它的运行
速度要快得多，可以通过多测几次来增加正确率。