的Java probablePrime性能

Question

的Javadoc上probablePrime：

返回正BigInteger的可能爲素數，與指定長度的 。 BigInteger由 返回的概率是複合的概率不超過2-100。

我的問題是，通過不保證素數的方式獲得多少性能，但幾乎可以確定它？此外，這種性能差異是否真的值得在未來某個時間發生錯誤的一分鐘機會？特別是如果加密的有效性取決於這個數字是素數。

Answer 1

probablePrime()的核心是一系列的Miller-Rabin測試（執行的循環次數取決於數字的位大小）並結合Lucas-Lehmer primality test。這些的時間複雜度取決於BigInteger實施的其餘部分。接受維基百科的「緩慢」估計值分別爲O（k log（n）^ 3）和O（log（n）^ 3）。另一方面，AKS-primality test，沒有未經證實的猜測，可以運行在Õ（log（n）^ 6）。

因此，假設您的數字足夠大，概率測試可能比確定性測試快得多。對於任何足夠大的密碼學來說，漸近行爲很可能是可觀察的。當然，唯一可以找到的方法是實施修改後的AKS並計算結果。

（k是Mille-Rabin中的週期數）。

Answer 2

如果你有這樣的：

特別是如果加密的有效性依賴於這個數字是 黃金

一種約束，那麼你不應該在我看來，使用probablePrime。因爲你不能保證算法的正確性。

但是如果獲得非素數的可能性非常低，例如與SHA-1 collision probability可比，那麼您對它沒有問題。 （如果你的git可以）

如果你在一個給定的範圍內使用素數池，那麼你可以預先生成素數列表並將它們放在查找表中。這會給你O(1)時間複雜度。