尋找 Sophie Germain 素數的高效算法

有效尋找大型 Sophie Germain 素數的行業標準是什麼？

作為我的應用程序中請求處理的一部分，我需要生成 Paillier 密鑰。

我目前的方法是生成一個q由 Miller-Rabin 測試支持的偽隨機素數，然後使用 Miller-Rabin 和 Baillie-PSW 設置p = 2q + 1並檢查是否p也是素數。重複此過程直到p是素數。

loop {
 q <- randomPrime(nbits - 1) // generates probably prime number, 
                             // performs Miller-Rabin tests on the result
 p = 2q + 1
 return if isPrime(p)  //applying the Miller-Rabin & Baillie-PSW tests 
}

在nbits = 1024我的筆記型電腦上，一個循環步驟大約需要 100 毫秒。還不錯，但為了找到想要的p，q我需要執行幾個循環步驟。迄今為止最好的結果是 156 次重試（約 16 秒），最差的結果是 1616 次重試（約 160 秒）。

這是一種高於所需延遲的方式，所以我想知道現在什麼被認為是正確的方法。

我不知道任何行業標準，但是很明顯您的程式碼不是最理想的。

初始 randomPrime() 將有效地選擇一個候選號 $ q $ ，然後花費大量時間確保該數字是素數。現在，有一半的時間它會選擇一個 $ q \equiv 1 \pmod 3 $ ; 如果是這樣，p 將是 3 的倍數，所以你只是浪費了所有時間來測試 if $ q $ 是素數。

現在，我見過的所有隨機素數常式首先確保它們的候選數沒有任何小因素（所以我們不需要對這些值進行昂貴的素數測試）；這可以通過計算來完成 $ q \bmod s $ 對於小素數 $ s $ ，或者通過創建一個篩子（一個點陣圖，其中每個位 $ i $ 對應一個值 $ a + bi $ ; 如果該位被標記 $ a + bi $ 有一個小因素）。

兩種方法都可以擴展為檢查 $ q $ 或者 $ p = 2q+1 $ 有一個小因素：

• 對於顯式 $ q \bmod s $ 計算，如果它是 0 或 $ (s-1)/2 $
• 對於篩子的情況，我們標記位 $ a + bi \bmod s $ 為 0 或 $ (s-1)/2 $

這樣做將顯著減少您需要執行的迭代次數。

現在，如果您的 randomPrime() 邏輯在您無法觸及的庫中，則此建議對您沒有幫助。但是，如果你能做到，這將是有幫助的。

引用自：https://crypto.stackexchange.com/questions/60329