素数判定算法的改进

张景龙,黄静,王爱松,张春生,赵琳娜,宝力高

（内蒙古民族大学,内蒙古通辽 028000）

素数在计算机公钥私钥加密中有着重要的应用,尤其在RSA公钥密码中,通常需要上百位甚至上千位的素数[1-2].对于一个较大的数,判断其是否是素数需要极大的计算量.如何快速地判断一个数是否为素数,有着重要的意义.

1 相关知识

1.1 素数的定义

为了在计算机中提高判断素数的效率,先从素数的定义开始研究.

素数,也称质数,是指在大于1的自然数中,除了1和此整数自身外,没法被其他自然数整除的数[3-5].从定义出发,判断自然数N是否为素数,应该用N去除从2到N-1所有的数.如果找不到能够整除N的整数,则N是素数,否则N不是素数.

1.2 由素数定义引出的算法

根据定义给出判断自然数N是否为素数的算法1如下：

（1）设定变量P=0,作为标志变量,P=0表示N为素数,P=1表示N不是素数；

（2）M=2 TO N-1循环执行（3）；

（3）如果N除以M的余数为零,则P=1,跳出循环到（4）；否则M+1→M,回到（2）；

（4）如果P=0,则N是素数,否则N不是素数.

很显然,利用算法1判断一个数是否为素数,其时间复杂度为O（N）.

1.3 判断素数的经典算法

事实上,除数M的范围可以进一步缩小,假如自然数N不是素数,则除1和其本身之外,必然至少存在两个数A和B,使得A×B=N,则A、B两个数中必有一个大于或等于根号N,一个小于或等于根号N.因此,只要用小于或等于根号N的整数（1除外）去除N即可[6-7],所以可将作为除数的变量M的取值范围缩小到2→[],改进的算法2如下：

（1）设定变量P=0,作为标志变量,P=0表示N为素数,P=1表示N不是素数；

（3）如果 N 除以 M 的商为零,则 P=1,跳出循环到（4）；否则 M+1→M,回到（2）；

（4）如果P=0,则N是素数,否则N不是素数.

1.4 素数的分类

算法2虽然是求素数的经典算法,其实这个算法还可以进一步改进.事实上,在两位以上的自然数中,只有个位是1、3、7、9的数才有可能是素数.为此,先将素数根据个位数值的情况进行分类.为了方便描述,定义 N1、N3、N7、N9 分别代表个位为 1、3、7、9 的自然数,分别表示为 N1=10×n+1,N3=10×n+3,N7=10×n+7,N9=10×n+9,其中n为大于等于1的自然数.

2 非素数质因数分析

非素数仅指个位为 1、3、7、9 的自然数,至于个位为 0、2、4、5、6、8 的自然数,肯定不是素数,所以不在分析之列.

2.1 N1的质因数

如果N1不是素数,则除了1和其本身之外,必然还至少存在两个自然数,并且这两个自然数的乘积等于N1.使乘积个位为1的情况只有以下3种可能性：

A1×B1=N1,其中A1、B1代表个位为1的自然数.

A3×B7=N1,其中A3、B7分别代表个位为3和7的自然数.

A9×B9=N1,其中A9、B9代表个位为9的自然数.

2.2 N3的质因数

如果N3不是素数,则除了1和其本身之外,必然还至少存在两个自然数,并且这两个自然数的乘积等于N3.使乘积个位为3的情况只有以下2种：

A1×B3=N3,其中A1、B3分别代表个位为1和3的自然数.

A7×B9=N3,其中A7、B9分别代表个位为7和9的自然数.

2.3 N7的质因数

如果N7不是素数,则除了1和其本身之外,必然还至少存在两个自然数,并且这两个自然数的乘积等于N7.使乘积个位为7的情况只有以下2种：

A1×B7=N7,其中A1、B7分别代表个位为1和7的自然数.

A3×B9=N7,其中A3、B9分别代表个位为3和9的自然数.所以判断N7是不是素数,除数M不必依次取2到[]的值,只需取其中个位为3、7（或3、1,或9、7,或9、1）的数即可.这样大大减少了循环次数,效率提高5倍.

式中：Δy(k+1)=y(k+1)-y(k)；Δu(k)=u(k)-u(k-1)；φ(k)——伪偏导数。

判断N3和N7是否为素数的方法可以合二为一.

2.4 N9的质因数

如果N9不是素数,则除了1和其本身之外,必然还至少存在两个自然数,并且这两个自然数的乘积等于N9.使乘积个位为9的情况只有以下3种：

A1×B9=N9,其中A1、B9分别代表个位为1和9的自然数

A3×B3=N9,其中A3、B3代表个位为3的自然数

A7×B7=N9,其中A7、B7代表个位为7的自然数所以判断N9是不是素数,除数M不必依次取2到[]的值,只需取其中个位为9、7、3（或7、3、1）的数即可.这样大大减少了循环次数,效率提高10/3倍.

3 改进的算法

3.1 改进的素数算法

基于上文的分析,判断一个两位以上的自然数N是否为素数,先取其个位,若个位数是0、2、4、5、6、8,则N一定不是素数,若个位是1、3、7、9,则根据不同的情况,进入不同的循环.只是增加了一次判断,但却提高效率10/3倍或5倍以上.

改进的算法（算法3）如下：

3.2 效率更高的素数算法

素数的判定算法3还可以进一步优化为算法4,优化主要考虑两方面：①算法3中作为除数的以1、3、7、9结尾的数中还有一些不是素数的数,如果把这些非素数从中去掉,可以进一步提高效率；②构造必要的素数表,借助于素数表可以提高计算效率.

根据数论的相关知识,合数可以分解为若干个素数的乘积,所以判断一个数N是否为素数,只需要用2～之间的素数去除即可.为进一步提高效率,在实际计算过程中,可以构建素数表T1、T2、T3…TK其中T1定义为10以内的素数表（将2和5去掉）,T2定义为100以内的素数表,T3定义为1 000以内的素数表,即T1={3,7},T2={3,7,11,13,17…97},T3={3,7,11,13……97,101,103,107…991,997},其它素数表以此类推.当然,除素数表1外,更高一级素数表的构建也使用算法4,为免去不必要的计算,T1中去掉素数2和5,原因很简单,因为素数只是以1、3、7、9结尾的,所以T1素数表中完全可以将2、5去掉,这对于生成T2、T3…TK在效率上有着显著提高.例如想计算 11～100 之间的素数,只需要将 11、13、17、19、21、23、27、29……91、93、97、99这36个数用3和7去除即可,实际运算次数只有54次,而使用经典算法运算次数为228次,所以算法4和经典算法（算法2）有着显著的提高.算法4描述如下：

（1）设定变量P=0,作为标志变量,P=0表示N为素数,P=1表示N不是素数；设定变量K,K为N的位数.如果 K=1,则 T1={3,7}.

（2）如果TK-1不存在,先计算生成TK-2；如果TK-1存在,M从素数表TK-1中依次取值循环执行（3）；

（4）取 TK-1中的下一数值回到（3）.如全部取完,则到（5）；

（5）如果P=0,则N是素数,否则N不是素数.

为了进一步提高计算效率,建议将T1、T2……生成素数表直接保存在文件中,使用时直接读入即可,这样可以免去递归调用算法的次数,从而提高效率.比如想求10 000以内的素数,只需要调用100以内的素数表即可.

4 小结

在判断两位以上的数是否为素数时,算法4确实比算法3、算法2和算法1效率高出许多,尤其是对于计算机公钥密码中,需要一个几百甚至上千位的素数,所选择的素数位数越多,加密的安全性就越高,所以改进判断素数的算法,提高效率是非常必要的.设计一个算法来判断一个数是否是素数以及对其质因子查找的效率,直接影响到计算机RSA加密可靠性,其实素数还是有着一定的内在规律,很多人提出针对某个有限范围的素数表示[10-13].将来也许有可能使用一种或几种形式的公式将所有的素数表示出来,至少可以找到构成素数的必要条件或者充分条件,那样就可以推导出运算效率更高的素数求解算法.

[1]卢开澄.计算机密码学[M].北京：清华大学出版社,2003.

[2]William S.密码编码学与网络安全——原理与实践[M].北京：电子工业出版社,2008.

[3]陈景润.初等数论（Ⅰ）[M].北京：科学出版社,1978.

[4]陈景润.初等数论（Ⅱ）[M].北京：科学出版社,1980.

[5]潘承洞,潘承彪.歌德巴赫猜想[M].北京：科学出版社,1981.

[6]谭浩强.C程序设计[M].北京：清华大学出版社,2005.

[7]张福炎.程序员级高级程序员级程序设计[M].北京：清华大学出版社,1993.

[8]潘承洞.初等数论[M].北京：北京大学出版社,1997.

[9]谭浩强,田淑清.BASIC语言程序设计[M].北京：科学普及出版社,1993.

[10]孙琦,旷京华.素数判定与大数分解[M].山东：教育出版社,1995.

[11]曹云飞,杨煜,邓小艳.一种素数产生算法[J].信息安全与通信保密,2007（8）：31-35.

[12]韦萍萍,戎士奎.判定素数的新方法及程序[J].贵州教育学院学报,2005（2）：1-3.

[13]王云葵.素数公式与Fermat素数的判别[J].商丘师范学院学报,2002（5）：39-40.