基于VB的大素數Solovay-Strassen檢測的設計與實現

彭韜 陳文慶

（1.廣東茂名幼兒師范?？茖W校 廣東省高州市 525200 2.嶺南師范學院數學與統計學院 廣東省湛江市 524048）

在互聯信息時代的今天，網絡改變了我們的生活方式，但隨之而來的網絡信息安全也存嚴重威協，信息安全也成為互聯網世界的熱點問題。信息的加密和解密碼是解決網絡信息安全的主要技術手段之一，而密鑰的選取是密碼學的關鍵。目前，對信息加密和解密的算法很多，但公鑰密碼體制是目前信息加密、解密和數字簽名技術中較為廣泛應用，因為公鑰密碼體制中具有較高的安全性(如RSA、ElGamal 等算法)。但RSA、ElGamal 等算法的公開密鑰和私有密鑰都需要大素數，因此，對大素數的選取在RSA、ElGamal應用中十分重要。信息的高度保密對密鑰位數要求越來越多（512位、1024 位或更多位數），也就是對素數的位數要求越來越大，而要判斷一個大整數是否為素數的難度也在不斷加強。此時，能否快速、有效地判斷一個大整數的屬性就顯得極為重要。

目前，大素數檢測方法有Solovay-Strassen 檢測法、Lehman 檢測法和Miller-Rabin 檢測法。而Solovay-Strassen 檢測法最為常用，而且該方法相對于其它概率性檢測法來說準確率更高[1-5][7-8]。本文主要探討如何在Visual Basic 環境下實現大素數的檢測，解決在應用系統開發時實現數據的加密和解密，以保證系統的信息安全。

1 Visual Basic整型數據類型和大整數的存儲

Visual Basic 有3 種整型基本數據類型，它們的性質和表示范圍如表1所示。

由表1 可以看出，長整型long 是Visual Basic 中最大整型數據類型，其存儲長度為4 字節即32 位二進制數，這樣的有效位數的整數遠遠不能滿足各種密碼體制的密鑰位數的需要，而Visual Basic不能直接存儲和運算超過32 位的整型數據。為了解決在Visual Basic 中可以實現大整數的存儲和運算，利用Visual Basic 中的動態數組來存放大整數，而且數組中每個元素的數據類型是long，其定義如下：

Dim Number( ) as Long

采用這種數據結構存儲整型數據，數組的元素個數是動態的，不受數量限制，理論上可以實現任位數的整型數據的存儲和運算。數組中每個元素存放4 字節整數，即是說每個數組元素就相當于存放32 位二進制數，且數組的元素個數不受限制，可以動態增加和減少，這樣大大提高了Visual Basic 中整型數據的表示范圍。

2 大素數的檢測方法

在公鑰密碼體制中，大素數的選取是構造公鑰和私鑰的關鍵。目前，大素數檢測方法可以分為確定性大素數檢測和概率性大素數檢測，但目前還沒有有效的確定性大素數檢測方法，概率性大素數檢測是目前大素數檢測的主要方法。

2.1 素數檢測方法的分類

目前，大素數的檢測方法有確定性和概率性大素數檢測兩種，確定性大素數檢測方法主要有基于Lucas 和Pocklington 定理的確定性素數檢測方法[3]。確定性大素數檢測方法產生的大整數必然是大素數，該方法的優點在于產生的數一定是大素數，但缺點是生成的大素數位數受到的限制(一般位數比較少等)，特別是如果算法設計不當，非常容易產生出有規律的素數，素數的變化規律非常容易被密碼破譯者破譯，直接破解到密碼系統所使用的素數，從而影響密碼的安全性。確定性大素數檢測方法的效率低且安全性非常差，因此，目前大素數檢測方法主要采用概率性檢測方法，其理論基礎是Fermat 小定理：若n 是素數，則對所有1 ≤a ≤n-1 的整數a，有a(n-1)mod n=1；該定理的逆否命題也成立，即a(n-1)mod n ≠1，則n 為合數。但從大量數據統計來看，如果滿足a(n-1)mod n=1，則n 為素數概率較大，但也存在n 原來是合數而被認為素數的可能性（小概率），即n 為偽素數。

這種方法的優點是：檢測大素數速度較快，構造的大素數沒有規律性，安全性能好，但其缺點就是其檢測的大素數具有一定的誤判，所以其檢測的素數又稱為偽素數。其中較為常用的算法有Fermat 檢測法、Lehman 檢測法和Solovay-Strassen 檢測法[1][3][6]。

2.2 Solovay-Strassen素數檢測的基本原理

Solovay-Strassen 素數檢測建立在以下兩個定理基礎之上的：

定理1：如果n>2 是一個素數，則對于任意整數a(0

成立[6]。

定理2：如果n>2 是一個奇合數，則至少有50%的，即，使得同余式不成立。

2.3 Solovay-Strassen素數檢測的基本算法

根據上述兩定理，Solovay-Strassen素數檢測算法具體描述如下：

對于待檢測奇整數n，執行以下操作：

2.3.1 對i 從1 到t 做循環

（1）選擇一個小于n 的隨機整數a(0

（3）如果r ≠1 或-1，則返回n 不是素數；

（4）計算Jacobi 符號[9,10]J(b,n)=(b/n)；

（5）如果r ≠(b/n)，返回n 不是素數。

2.3.2 返回n 是素數

2.4 Solovay-Strassen素數檢測算法分析

3 Solovay-Strassen大素數檢測程序的實現

在Solovay-Strassen 素性檢測算法中關鍵一步就是r=a(n-1)(mod n)，如果采用逐次求冪取模的計算方式，時間復雜度是O(n)，為了提高素數檢測效率，本文對算法作了優化。充分利用每次循環過程中的中間結果為下一步計算提供數據。例如計算過程a2(mod n)，a4(mod n)，a8(mod n)，……，等中間結果可以保存到數組中。這樣，其后的計算可以充分這些中間結果，例如計算a254(mod 255)時，就可以根據已保存的中間結果計算a254= a128*a64*a32*a16*a8* a4*a2(mod 255)。

本文為了提高模冪計算效率，先計算ai(mod n)的記錄于一個表中，其i 是2 的冪次，然后將n-1 轉化為二進制表示并由低位到高位存儲于數組中，初始值為1，遍歷數組，如果某位是1 時則把表中對應位置的ai(mod n)乘以r 并賦值給r，如此循環，即可得到a(n-1)(mod n)值，大大提高了計算模冪運算速度。例如，計算a64(mod n)則要循環64 次模冪運算，改進后則需要進行a2，a4，a8，a16，a32，a64(mod n)共計6 次模冪計算即可。大大提高了測試效率，時間復雜度也由原來的O(n)降到O(logn)。

大素數Solovay-Strassen 測試方法的Visual Basic 程序如下：

4 結束語

本文主要討論了Solovay-Strassen 檢測大素數方法的基本理論和算法，并在Visual Basic 環境下采用動態數組實現了大素數Solovay-Strassen 檢測算法。本文中只給出了Solovay-Strassen 大素數檢測方法的核心代碼，在完整的檢測代碼包括大整數運算、模冪運算等函數，篇幅較長，本文沒有詳盡給出。