整数素性测试的研究

摘要：本文探索和研究了素性判定的理论方法，给出了朴素判断素数等六种素性测试方法，最后通过改进程序算法，与确定性素性测试方法进行比较，取得了较为理想的结果。

关键词：素性测试 概率算法 C-free

1.素数的概述

根据素数的定义，因数只有1和它本身的整数叫为素数。一个基本问题是如何有效地确定一个数是否是一个素数，即素性测试问题。最简单的办法就是直接利用素数的定义来判断。但对于大素数来说，由于计算量太大，根本无法实现用于具体的应用系统中。故需要根据素数判断的理论研究新的程序算法，以此来提高素数判断的效率。

2.素性判定的方法

①朴素判断素数。根据素数的定义，假设一个整数为n，从2到n-1的整数都枚举一遍，判断是否存在能整除n的整数，如果都不能则n为素数。

容易发现，用这种方法判断整数n是否为素数需要n-2次判断。在n非常大或者测试量很大时，这种方法显然不可取。

②改进朴素判断素数。对于一个小于n的整数x，如果n不能整除x，则n必然不能整除n/x。反之相同。所以按照素数定义来判断素数时，可以进行一个较为明显的优化。即我们只需从2枚举到 。因为在判断2的同时也判断了n/2，……，以此类推，到 时，把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环境下实现的，在更短的时间内判定大整数是否为素数，即：

在整数位数较少、整数数目不多的情况下，用该算法不能明显体现其优越性，因此随机取出100个16-18位大整数，在同一批数据的情况下，对于这个概率性算法与确定性算法，比较跑完所用的时间以及检测的正确性。

随机给出100组整数，用概率性算法和确定性算法测试，下面是两者在C-free环境中运行后的部分结果：

经多次试验，增加整数位数和整数数量（即大整数），两种算法所需时间都增加了，但在大整数前提下，显然新概率性算法跑完的时间远小于传统的确定性算法，这样就能大幅度提高素性测试的效率。而且在测试这100个整数时，最后发现两组结果一样。

确定性算法对于素性判定的正确率很高，但随着整数的变大，其运行速度随之也减慢。而在改进的概率性程序算法中，它的运行速度要快得多，可以通过多测几次来增加正确率。

4.总结

素性测试问题不仅在数学上是一个有挑战性的问题，而且在实际应用系统中也具有十分重要的地位。本文是在研究前人的文献后，采用了一种较为快速有效的素性测试方法，使得在保证正确率较高的情况下，花费的时间减少，为科学工作者和教学工作者带去一定方便。

参考文献

[1]谢文平，陈大钊，大整数素性的计算机测试和软件实现[J].南华大学学报

[2]Thomas H.CormenCharles E.leiserson Ronald L.Rivest Clifoord Stein，Introduction to Algorithms（Second Edition），China Machine Press