基于頻率的大素數(shù)高效生成算法

湯鵬志，李 彪

（華東交通大學基礎科學學院，江西南昌330013）

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

1 構建素數(shù)庫

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

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

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

推論1 在Eratosthenes篩法中對尋求到的第一個素數(shù)k，在區(qū)間(1 ，k2)沒有被劃掉的數(shù)均為素數(shù)。

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

2 素數(shù)的頻率分布

素數(shù)具有無窮多個，并且隨區(qū)間變大而逐漸變得稀疏。通過運行素數(shù)庫構建算法，得到區(qū)間(0 ，109)中的素數(shù)庫，從而考察素數(shù)的尾數(shù)分布情況。

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

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

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

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

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

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

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

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

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

3 素數(shù)檢驗算法分析

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

表4 素數(shù)檢驗算法分析情況Tab.4 Analysis of prime number inspection algorithm

4 大素數(shù)生成算法

通過改進ISO/IEC標準[12]，得出一種高效的大素數(shù)生成算法。在實際的工程中，如若需要生成一個1 024位（二進制數(shù)）的素數(shù)q，則必須滿足，其中。依據(jù)分析，滿足表達式2×3×5×…×509k+1(k∈N)的整數(shù)已經(jīng)濾掉了所有小于512的素因子，該數(shù)在生成時就已經(jīng)過濾掉80%以上的非素數(shù)。在素數(shù)的生成和檢驗算法實施前，需要計算參數(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，保證篩選的范圍內的整數(shù)的個數(shù)，必須對n的數(shù)量級進行分析。由于n=2×3×5×…×503×509＜21×22×23×…×210×210=2746，則在篩選的范圍中存在的整數(shù)個數(shù)i=21023/2746=2277個。在如此大的區(qū)間中，一定能夠找到若干個素數(shù)。算法如下

5 結論分析

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

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

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

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

[2]潘峰，申軍偉.一種強素數(shù)因子分解的量子算法[J].計算機工程與應用，2010，46（10）:73-77.

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

[4]王名利.自然數(shù)是否為素數(shù)的兩個判定方法[J].數(shù)學通報，2010，49（6）:47-49.

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

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

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

[8]夏靜波，陳建華.一種快速的素數(shù)生成和檢驗算法[J].武漢大學學報:理學版，2005，52（S2）:25-27.

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

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

[11]游新娥.RSA算法中安全大素數(shù)生成方法研究與改進[J].北京電子科技學院學報，2007，15（2）:14-16.

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