我可以使用這個過程選擇一個大的隨機素數嗎？

假設我想要一個隨機的 1024 位素數 $ p $ . 顯然正確的方法是選擇一個隨機的 1024 位數字並使用通常眾所周知的測試來測試它的素數。

但假設我這樣做：

1. 選擇隨機奇數 1024 位數字 $ n $
2. 如果 $ n $ 是素數，返回 $ n $
3. $ n \leftarrow n+2 $
4. 轉到 2

（這種方法允許通過篩分更快地選擇素數。）

由於素數在數軸上不是均勻分佈的，因此該算法似乎更喜歡在長時間複合後存在的素數。取一塊數線繞 $ 2^{1024} $ x 表示素數：

—xx—————————-x—————– ——–x—x

顯然，我們上面的算法更容易找到上面的第三個素數，而不是找到第二個素數。

**問題：**這是一個問題嗎？

此過程稱為增量搜尋，並在《應用密碼學手冊》（註釋 4.51，第 148 頁）中進行了描述。儘管選擇某些素數的機率高於其他素數，但這不允許對 RSA 進行已知攻擊；粗略地說，增量搜尋會選擇本來可​​以選擇的素數，並且仍然有數以億計的素數。OpenSSL使用這種素數生成技術。

不，這不被認為是一個問題，可能是因為：

• 沒有已知的分解方法可以利用偏差
• 至少，當您將其與素數的數量進行比較時，偏差實際上並沒有那麼大。給定周圍素數的密度 $ 2^{1024} $ , 可能有緊隨其後的素數 $ 2000 $ 連續奇數複合；這樣一個素數的機率約為 $ 2000/2^{1022} \approx 2^{-1011} $ 被選中。在另一個極端，緊跟在另一個素數（孿生素數）之後的素數的機率為 $ 2^{-1022} $ 被選中。看起來不會有那麼大的區別 $ 2^{-1011} $ 和 $ 2^{-1022} $ .

此外，尋找素數的現有標準（X9.31，X9.80）支持上述類型的線性搜尋（即使它們在某些細節上有所不同，例如增量不是二，而是其他偶數）。

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