湯鵬志，李 彪

（華東交通大學(xué)基礎(chǔ)科學(xué)學(xué)院，江西南昌330013）

1977年Ron Rivest、Adi Shamirh和Len Adleman提出公鑰密碼體制（RSA）加解密算法，其安全性在于在計(jì)算機(jī)上生成兩個(gè)足夠長(zhǎng)度的大素?cái)?shù)，其乘積具難分解性[1-2]。目前，素?cái)?shù)確定性算法主要分為遞歸試除法，Eratosthenes篩法，Miller檢驗(yàn)和多項(xiàng)式時(shí)間內(nèi)判定的素?cái)?shù)（AKS）算法。文獻(xiàn)[3]分析表明，Eratosthenes篩法是一種較好的素?cái)?shù)確定性算法。根據(jù)文獻(xiàn)[4]，任意素?cái)?shù)（除2和3）均可表示為的理論，可提升篩法效率。生成大素?cái)?shù)的方法是隨機(jī)產(chǎn)生一個(gè)大整數(shù)，然后進(jìn)行素性檢測(cè)。文獻(xiàn)[5]提出一種用概率方法來(lái)研究素?cái)?shù)的分布，是提升大整數(shù)素性的有效途徑。常用的素?cái)?shù)檢驗(yàn)算法主要為Fermart算法、Solovay-Strassen檢測(cè)法、Lehman檢測(cè)法、Miller檢驗(yàn)、Miller-Rabin檢測(cè)法和AKS算法[6]。通過(guò)分析當(dāng)今的大素?cái)?shù)生成方法與原理[7-11]，提升大整數(shù)的素性和選擇優(yōu)良的素?cái)?shù)檢驗(yàn)算法，從而提出一種改進(jìn)的大素?cái)?shù)的高效生成算法。

1 構(gòu)建素?cái)?shù)庫(kù)

對(duì)素?cái)?shù)的分布頻率研究，需建立在素?cái)?shù)庫(kù)的基礎(chǔ)之上。在素?cái)?shù)的研究領(lǐng)域中，確定性素?cái)?shù)算法存在很多，如試除法，Eratosthenes篩選法，Miller檢驗(yàn)，AKS算法等。在素?cái)?shù)算法中，Eratosthenes篩法應(yīng)用非常廣泛。傳統(tǒng)Eratosthenes篩法需要對(duì)每個(gè)數(shù)依次比較，算法的效率較為低下，通過(guò)對(duì)Eratosthenes篩法進(jìn)行優(yōu)化，得出素?cái)?shù)庫(kù)構(gòu)建算法。

定理1 除2和3之外，素?cái)?shù)均可表示成6k±1(k∈N)的形式。

定理2 如果k為素?cái)?shù)，則k×j(j∈N+)必為合數(shù)。

推論1 在Eratosthenes篩法中對(duì)尋求到的第一個(gè)素?cái)?shù)k，在區(qū)間(1 ，k2)沒(méi)有被劃掉的數(shù)均為素?cái)?shù)。

定義一個(gè)bool型素?cái)?shù)判定數(shù)組p[n+1]。根據(jù)定理1，當(dāng)i=2或i=3或i=6k+1或時(shí)，p[i]=true；否則p[i]=false。尋找第一個(gè)p[i]=true(i∶ 5?n)的素?cái)?shù)i，i的倍數(shù)均為合數(shù)。另外，數(shù)組賦值時(shí)已去除偶數(shù)，將內(nèi)層循環(huán)j限定為奇數(shù)。故當(dāng)素?cái)?shù)為時(shí)，有。最后所有滿足的i就是區(qū)間的所有素?cái)?shù)。算法如下

2 素?cái)?shù)的頻率分布

素?cái)?shù)具有無(wú)窮多個(gè)，并且隨區(qū)間變大而逐漸變得稀疏。通過(guò)運(yùn)行素?cái)?shù)庫(kù)構(gòu)建算法，得到區(qū)間(0 ，109)中的素?cái)?shù)庫(kù)，從而考察素?cái)?shù)的尾數(shù)分布情況。

定義1 在某個(gè)區(qū)間范圍內(nèi)，用素?cái)?shù)模100的余數(shù)進(jìn)行分類，各類余數(shù)中擁有素?cái)?shù)的個(gè)數(shù)稱為素模百頻數(shù)。

表1 各區(qū)間的素模百頻數(shù)Tab.1 Frequency of module in various regions

通過(guò)表1可知，素?cái)?shù)尾數(shù)的分布大致相同，即任何尾數(shù)在區(qū)間中所占的素?cái)?shù)的概率是同等的。如若一個(gè)整數(shù)在生成之時(shí)，已經(jīng)排除存在部分素因子，則它是素?cái)?shù)的可能性會(huì)更大。

定義2 在某個(gè)區(qū)間范圍內(nèi)，滿足表達(dá)式ΠPi×k+1（Pi為小素?cái)?shù)）的整數(shù)中，所占素?cái)?shù)的個(gè)數(shù)稱為素積頻數(shù)。

表2 各區(qū)間的素積頻數(shù)Tab.2 Frequency of prime number in various regions

通過(guò)觀察表2中的數(shù)據(jù)，隨著過(guò)濾的素因子的個(gè)數(shù)增加，區(qū)間內(nèi)的素積頻數(shù)逐漸減少。但隨著表達(dá)式過(guò)濾素因子的個(gè)數(shù)增加，無(wú)法清晰得到該表達(dá)式下整數(shù)是素?cái)?shù)的可能性變化狀況。

定義3 在某個(gè)區(qū)間中，滿足表達(dá)式ΠPi×k+1（Pi為小素?cái)?shù)）的素積頻數(shù)與整數(shù)個(gè)數(shù)比值，稱為素積頻率。

表3 各區(qū)間的素積頻率Tab.3 Frequency of prime number in various regions %

通過(guò)分析表3中的數(shù)據(jù)，隨著過(guò)濾的素因子的個(gè)數(shù)增加，區(qū)間內(nèi)的素積頻率逐漸增大。通過(guò)實(shí)踐表明:采用小于512的素?cái)?shù)可以淘汰大約82%的非素整數(shù)。

3 素?cái)?shù)檢驗(yàn)算法分析

素?cái)?shù)檢驗(yàn)算法分為確定性檢驗(yàn)算法和概率檢驗(yàn)算法。通過(guò)確定性檢驗(yàn)算法的得到的數(shù)一定是素?cái)?shù)，Miller檢驗(yàn)和AKS算法就是常用的確定性算方法。通過(guò)概率性檢驗(yàn)算法得到的數(shù)只是偽素?cái)?shù)，F(xiàn)ermart算法、Solovay-Strassen檢測(cè)法、Lehman檢測(cè)法和Miller-Rabin檢測(cè)法是現(xiàn)今流行的概率算法。確定性檢驗(yàn)算法需要深厚的數(shù)學(xué)理論基礎(chǔ)，算法的實(shí)現(xiàn)相當(dāng)復(fù)雜。而概率檢驗(yàn)算法雖然存在一定的概率得到偽素?cái)?shù)，但經(jīng)過(guò)多次測(cè)試可將報(bào)錯(cuò)率控制在極低的范圍內(nèi)。通過(guò)表4的算法分析，可知Miller-Rabin算法是素?cái)?shù)檢驗(yàn)算法中的最佳選擇。

表4 素?cái)?shù)檢驗(yàn)算法分析情況Tab.4 Analysis of prime number inspection algorithm

4 大素?cái)?shù)生成算法

通過(guò)改進(jìn)ISO/IEC標(biāo)準(zhǔn)[12]，得出一種高效的大素?cái)?shù)生成算法。在實(shí)際的工程中，如若需要生成一個(gè)1 024位（二進(jìn)制數(shù)）的素?cái)?shù)q，則必須滿足，其中。依據(jù)分析，滿足表達(dá)式2×3×5×…×509k+1(k∈N)的整數(shù)已經(jīng)濾掉了所有小于512的素因子，該數(shù)在生成時(shí)就已經(jīng)過(guò)濾掉80%以上的非素?cái)?shù)。在素?cái)?shù)的生成和檢驗(yàn)算法實(shí)施前，需要計(jì)算參數(shù)m，n，kj，其中1≤j≤97且j∈N，m=2k1×3k2×5k3×…×503k96×509k97，n=2×3×5×…×503×509，并且m必須滿足m+1≥qmin。在算法中，每迭代一次整數(shù)q需要加n，其中q=q+n，保證篩選的范圍內(nèi)的整數(shù)的個(gè)數(shù)，必須對(duì)n的數(shù)量級(jí)進(jìn)行分析。由于n=2×3×5×…×503×509＜21×22×23×…×210×210=2746，則在篩選的范圍中存在的整數(shù)個(gè)數(shù)i=21023/2746=2277個(gè)。在如此大的區(qū)間中，一定能夠找到若干個(gè)素?cái)?shù)。算法如下

5 結(jié)論分析

本文提出了一種對(duì)素?cái)?shù)尾數(shù)的分類頻數(shù)和表達(dá)式下素?cái)?shù)頻率的分析方法，通過(guò)小素?cái)?shù)對(duì)整數(shù)進(jìn)行初次過(guò)濾，經(jīng)過(guò)對(duì)素?cái)?shù)檢驗(yàn)算法的全面剖析，最后使用Miller-Rabin算法對(duì)形如ΠPim×n+1（Pi為小素?cái)?shù)）的整數(shù)進(jìn)行檢驗(yàn)。算法中通過(guò)利用1 024位和746位的兩個(gè)大整數(shù)空間存儲(chǔ)中間數(shù)據(jù)，跳躍大整數(shù)含有小素?cái)?shù)因子的可能，降低算法的循環(huán)遍歷次數(shù)，從而提升了算法的運(yùn)行效率。

表5數(shù)據(jù)表明，本文的大素?cái)?shù)生成算法可以快速的生成若干個(gè)大素?cái)?shù)，從而為RSA加解密算法提供強(qiáng)有力的安全保障。

表5 生成1 024 bit素?cái)?shù)的性能比較Tab.5 Performance comparison of forming prime number 1024 bit

[1]ARTO SALOMAA.公鑰密碼學(xué)[M].北京:國(guó)防工業(yè)出版社，1988:28-45.

[2]潘峰，申軍偉.一種強(qiáng)素?cái)?shù)因子分解的量子算法[J].計(jì)算機(jī)工程與應(yīng)用，2010，46（10）:73-77.

[3]HENRI COHEN.Acourse in computational algebraic number theory[M].北京:世界圖書(shū)出版公司，1996:17-36.

[4]王名利.自然數(shù)是否為素?cái)?shù)的兩個(gè)判定方法[J].數(shù)學(xué)通報(bào)，2010，49（6）:47-49.

[5]宋富高.雙重概率篩法與素?cái)?shù)分布[J].深圳大學(xué)學(xué)報(bào):理工版，2003，20（4）:61-107.

[6]秦曉東，辛運(yùn)幃，盧桂章.Miller-Rabin算法研究與優(yōu)化實(shí)現(xiàn)[J].計(jì)算機(jī)工程，2002，28（10）:55-57.

[7]張四蘭，夏靜波，余榮威.可信賴的高效素?cái)?shù)生成和檢驗(yàn)算法[J].計(jì)算機(jī)工程與應(yīng)用，2005，41（30）:31-34.

[8]夏靜波，陳建華.一種快速的素?cái)?shù)生成和檢驗(yàn)算法[J].武漢大學(xué)學(xué)報(bào):理學(xué)版，2005，52（S2）:25-27.

[9]張宏，劉曉霞，張若巖.RSA公鑰密碼體制中安全大素?cái)?shù)的生成[J].計(jì)算機(jī)技術(shù)與發(fā)展，2008，18（9）:131-134.

[10]戴經(jīng)國(guó)，張韶華，易葉青，等.生成大素?cái)?shù)的一個(gè)方法[J].科學(xué)技術(shù)與工程，2007，7（14）:3510-3511.

[11]游新娥.RSA算法中安全大素?cái)?shù)生成方法研究與改進(jìn)[J].北京電子科技學(xué)院學(xué)報(bào)，2007，15（2）:14-16.

[12]ISO/IEC.WD 18032-2000 Prime number generation[S].United States:FASchermer，2002.