素?cái)?shù)判定算法的改進(jìn)

張景龍,黃靜,王愛松,張春生,趙琳娜,寶力高

（內(nèi)蒙古民族大學(xué),內(nèi)蒙古通遼 028000）

素?cái)?shù)在計(jì)算機(jī)公鑰私鑰加密中有著重要的應(yīng)用,尤其在RSA公鑰密碼中,通常需要上百位甚至上千位的素?cái)?shù)[1-2].對于一個(gè)較大的數(shù),判斷其是否是素?cái)?shù)需要極大的計(jì)算量.如何快速地判斷一個(gè)數(shù)是否為素?cái)?shù),有著重要的意義.

1 相關(guān)知識

1.1 素?cái)?shù)的定義

為了在計(jì)算機(jī)中提高判斷素?cái)?shù)的效率,先從素?cái)?shù)的定義開始研究.

素?cái)?shù),也稱質(zhì)數(shù),是指在大于1的自然數(shù)中,除了1和此整數(shù)自身外,沒法被其他自然數(shù)整除的數(shù)[3-5].從定義出發(fā),判斷自然數(shù)N是否為素?cái)?shù),應(yīng)該用N去除從2到N-1所有的數(shù).如果找不到能夠整除N的整數(shù),則N是素?cái)?shù),否則N不是素?cái)?shù).

1.2 由素?cái)?shù)定義引出的算法

根據(jù)定義給出判斷自然數(shù)N是否為素?cái)?shù)的算法1如下：

（1）設(shè)定變量P=0,作為標(biāo)志變量,P=0表示N為素?cái)?shù),P=1表示N不是素?cái)?shù)；

（2）M=2 TO N-1循環(huán)執(zhí)行（3）；

（3）如果N除以M的余數(shù)為零,則P=1,跳出循環(huán)到（4）；否則M+1→M,回到（2）；

（4）如果P=0,則N是素?cái)?shù),否則N不是素?cái)?shù).

很顯然,利用算法1判斷一個(gè)數(shù)是否為素?cái)?shù),其時(shí)間復(fù)雜度為O（N）.

1.3 判斷素?cái)?shù)的經(jīng)典算法

事實(shí)上,除數(shù)M的范圍可以進(jìn)一步縮小,假如自然數(shù)N不是素?cái)?shù),則除1和其本身之外,必然至少存在兩個(gè)數(shù)A和B,使得A×B=N,則A、B兩個(gè)數(shù)中必有一個(gè)大于或等于根號N,一個(gè)小于或等于根號N.因此,只要用小于或等于根號N的整數(shù)（1除外）去除N即可[6-7],所以可將作為除數(shù)的變量M的取值范圍縮小到2→[],改進(jìn)的算法2如下：

（1）設(shè)定變量P=0,作為標(biāo)志變量,P=0表示N為素?cái)?shù),P=1表示N不是素?cái)?shù)；

（3）如果 N 除以 M 的商為零,則 P=1,跳出循環(huán)到（4）；否則 M+1→M,回到（2）；

（4）如果P=0,則N是素?cái)?shù),否則N不是素?cái)?shù).

1.4 素?cái)?shù)的分類

算法2雖然是求素?cái)?shù)的經(jīng)典算法,其實(shí)這個(gè)算法還可以進(jìn)一步改進(jìn).事實(shí)上,在兩位以上的自然數(shù)中,只有個(gè)位是1、3、7、9的數(shù)才有可能是素?cái)?shù).為此,先將素?cái)?shù)根據(jù)個(gè)位數(shù)值的情況進(jìn)行分類.為了方便描述,定義 N1、N3、N7、N9 分別代表個(gè)位為 1、3、7、9 的自然數(shù),分別表示為 N1=10×n+1,N3=10×n+3,N7=10×n+7,N9=10×n+9,其中n為大于等于1的自然數(shù).

2 非素?cái)?shù)質(zhì)因數(shù)分析

非素?cái)?shù)僅指個(gè)位為 1、3、7、9 的自然數(shù),至于個(gè)位為 0、2、4、5、6、8 的自然數(shù),肯定不是素?cái)?shù),所以不在分析之列.

2.1 N1的質(zhì)因數(shù)

如果N1不是素?cái)?shù),則除了1和其本身之外,必然還至少存在兩個(gè)自然數(shù),并且這兩個(gè)自然數(shù)的乘積等于N1.使乘積個(gè)位為1的情況只有以下3種可能性：

A1×B1=N1,其中A1、B1代表個(gè)位為1的自然數(shù).

A3×B7=N1,其中A3、B7分別代表個(gè)位為3和7的自然數(shù).

A9×B9=N1,其中A9、B9代表個(gè)位為9的自然數(shù).

2.2 N3的質(zhì)因數(shù)

如果N3不是素?cái)?shù),則除了1和其本身之外,必然還至少存在兩個(gè)自然數(shù),并且這兩個(gè)自然數(shù)的乘積等于N3.使乘積個(gè)位為3的情況只有以下2種：

A1×B3=N3,其中A1、B3分別代表個(gè)位為1和3的自然數(shù).

A7×B9=N3,其中A7、B9分別代表個(gè)位為7和9的自然數(shù).

2.3 N7的質(zhì)因數(shù)

如果N7不是素?cái)?shù),則除了1和其本身之外,必然還至少存在兩個(gè)自然數(shù),并且這兩個(gè)自然數(shù)的乘積等于N7.使乘積個(gè)位為7的情況只有以下2種：

A1×B7=N7,其中A1、B7分別代表個(gè)位為1和7的自然數(shù).

A3×B9=N7,其中A3、B9分別代表個(gè)位為3和9的自然數(shù).所以判斷N7是不是素?cái)?shù),除數(shù)M不必依次取2到[]的值,只需取其中個(gè)位為3、7（或3、1,或9、7,或9、1）的數(shù)即可.這樣大大減少了循環(huán)次數(shù),效率提高5倍.

式中：Δy(k+1)=y(k+1)-y(k)；Δu(k)=u(k)-u(k-1)；φ(k)——偽偏導(dǎo)數(shù)。

判斷N3和N7是否為素?cái)?shù)的方法可以合二為一.

2.4 N9的質(zhì)因數(shù)

如果N9不是素?cái)?shù),則除了1和其本身之外,必然還至少存在兩個(gè)自然數(shù),并且這兩個(gè)自然數(shù)的乘積等于N9.使乘積個(gè)位為9的情況只有以下3種：

A1×B9=N9,其中A1、B9分別代表個(gè)位為1和9的自然數(shù)

A3×B3=N9,其中A3、B3代表個(gè)位為3的自然數(shù)

A7×B7=N9,其中A7、B7代表個(gè)位為7的自然數(shù)所以判斷N9是不是素?cái)?shù),除數(shù)M不必依次取2到[]的值,只需取其中個(gè)位為9、7、3（或7、3、1）的數(shù)即可.這樣大大減少了循環(huán)次數(shù),效率提高10/3倍.

3 改進(jìn)的算法

3.1 改進(jìn)的素?cái)?shù)算法

基于上文的分析,判斷一個(gè)兩位以上的自然數(shù)N是否為素?cái)?shù),先取其個(gè)位,若個(gè)位數(shù)是0、2、4、5、6、8,則N一定不是素?cái)?shù),若個(gè)位是1、3、7、9,則根據(jù)不同的情況,進(jìn)入不同的循環(huán).只是增加了一次判斷,但卻提高效率10/3倍或5倍以上.

改進(jìn)的算法（算法3）如下：

3.2 效率更高的素?cái)?shù)算法

素?cái)?shù)的判定算法3還可以進(jìn)一步優(yōu)化為算法4,優(yōu)化主要考慮兩方面：①算法3中作為除數(shù)的以1、3、7、9結(jié)尾的數(shù)中還有一些不是素?cái)?shù)的數(shù),如果把這些非素?cái)?shù)從中去掉,可以進(jìn)一步提高效率；②構(gòu)造必要的素?cái)?shù)表,借助于素?cái)?shù)表可以提高計(jì)算效率.

根據(jù)數(shù)論的相關(guān)知識,合數(shù)可以分解為若干個(gè)素?cái)?shù)的乘積,所以判斷一個(gè)數(shù)N是否為素?cái)?shù),只需要用2～之間的素?cái)?shù)去除即可.為進(jìn)一步提高效率,在實(shí)際計(jì)算過程中,可以構(gòu)建素?cái)?shù)表T1、T2、T3…TK其中T1定義為10以內(nèi)的素?cái)?shù)表（將2和5去掉）,T2定義為100以內(nèi)的素?cái)?shù)表,T3定義為1 000以內(nèi)的素?cái)?shù)表,即T1={3,7},T2={3,7,11,13,17…97},T3={3,7,11,13……97,101,103,107…991,997},其它素?cái)?shù)表以此類推.當(dāng)然,除素?cái)?shù)表1外,更高一級素?cái)?shù)表的構(gòu)建也使用算法4,為免去不必要的計(jì)算,T1中去掉素?cái)?shù)2和5,原因很簡單,因?yàn)樗財(cái)?shù)只是以1、3、7、9結(jié)尾的,所以T1素?cái)?shù)表中完全可以將2、5去掉,這對于生成T2、T3…TK在效率上有著顯著提高.例如想計(jì)算 11～100 之間的素?cái)?shù),只需要將 11、13、17、19、21、23、27、29……91、93、97、99這36個(gè)數(shù)用3和7去除即可,實(shí)際運(yùn)算次數(shù)只有54次,而使用經(jīng)典算法運(yùn)算次數(shù)為228次,所以算法4和經(jīng)典算法（算法2）有著顯著的提高.算法4描述如下：

（1）設(shè)定變量P=0,作為標(biāo)志變量,P=0表示N為素?cái)?shù),P=1表示N不是素?cái)?shù)；設(shè)定變量K,K為N的位數(shù).如果 K=1,則 T1={3,7}.

（2）如果TK-1不存在,先計(jì)算生成TK-2；如果TK-1存在,M從素?cái)?shù)表TK-1中依次取值循環(huán)執(zhí)行（3）；

（4）取 TK-1中的下一數(shù)值回到（3）.如全部取完,則到（5）；

（5）如果P=0,則N是素?cái)?shù),否則N不是素?cái)?shù).

為了進(jìn)一步提高計(jì)算效率,建議將T1、T2……生成素?cái)?shù)表直接保存在文件中,使用時(shí)直接讀入即可,這樣可以免去遞歸調(diào)用算法的次數(shù),從而提高效率.比如想求10 000以內(nèi)的素?cái)?shù),只需要調(diào)用100以內(nèi)的素?cái)?shù)表即可.

4 小結(jié)

在判斷兩位以上的數(shù)是否為素?cái)?shù)時(shí),算法4確實(shí)比算法3、算法2和算法1效率高出許多,尤其是對于計(jì)算機(jī)公鑰密碼中,需要一個(gè)幾百甚至上千位的素?cái)?shù),所選擇的素?cái)?shù)位數(shù)越多,加密的安全性就越高,所以改進(jìn)判斷素?cái)?shù)的算法,提高效率是非常必要的.設(shè)計(jì)一個(gè)算法來判斷一個(gè)數(shù)是否是素?cái)?shù)以及對其質(zhì)因子查找的效率,直接影響到計(jì)算機(jī)RSA加密可靠性,其實(shí)素?cái)?shù)還是有著一定的內(nèi)在規(guī)律,很多人提出針對某個(gè)有限范圍的素?cái)?shù)表示[10-13].將來也許有可能使用一種或幾種形式的公式將所有的素?cái)?shù)表示出來,至少可以找到構(gòu)成素?cái)?shù)的必要條件或者充分條件,那樣就可以推導(dǎo)出運(yùn)算效率更高的素?cái)?shù)求解算法.

[1]盧開澄.計(jì)算機(jī)密碼學(xué)[M].北京：清華大學(xué)出版社,2003.

[2]William S.密碼編碼學(xué)與網(wǎng)絡(luò)安全——原理與實(shí)踐[M].北京：電子工業(yè)出版社,2008.

[3]陳景潤.初等數(shù)論（Ⅰ）[M].北京：科學(xué)出版社,1978.

[4]陳景潤.初等數(shù)論（Ⅱ）[M].北京：科學(xué)出版社,1980.

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

[6]譚浩強(qiáng).C程序設(shè)計(jì)[M].北京：清華大學(xué)出版社,2005.

[7]張福炎.程序員級高級程序員級程序設(shè)計(jì)[M].北京：清華大學(xué)出版社,1993.

[8]潘承洞.初等數(shù)論[M].北京：北京大學(xué)出版社,1997.

[9]譚浩強(qiáng),田淑清.BASIC語言程序設(shè)計(jì)[M].北京：科學(xué)普及出版社,1993.

[10]孫琦,曠京華.素?cái)?shù)判定與大數(shù)分解[M].山東：教育出版社,1995.

[11]曹云飛,楊煜,鄧小艷.一種素?cái)?shù)產(chǎn)生算法[J].信息安全與通信保密,2007（8）：31-35.

[12]韋萍萍,戎士奎.判定素?cái)?shù)的新方法及程序[J].貴州教育學(xué)院學(xué)報(bào),2005（2）：1-3.

[13]王云葵.素?cái)?shù)公式與Fermat素?cái)?shù)的判別[J].商丘師范學(xué)院學(xué)報(bào),2002（5）：39-40.