強素數的產生
似乎很難找到大的（超過 1024 位）強素數，或者至少是這樣的素數 $ p $ 在哪裡 $ (p-1) $ 有一個很大的素因數。有沒有關於強素數與其他素數分佈的資訊？GNU 庫為 RSA 生成強素數？
Quoth Messrs. Rivest、Shamir 和 Adleman 在 1978 年：
找到一個素數 $ p $ 這樣 $ (p - 1) $ 有一個很大的素數，生成一個很大的隨機素數 $ u $ ，然後讓 $ p $ 成為序列中的第一個素數 $ i \cdot u + 1 $ ， 為了 $ i = 2, 4, 6, \dots $ . （這不應該花費太長時間）。通過確保提供額外的安全性 $ (u - 1) $ 也有很大的素因數。
高速電腦可以在幾秒鐘內確定一個 100 位數字是否是素數，並且可以在一兩分鐘內找到給定點之後的第一個素數。
Quoth Messrs. Rivest 和 Silverman 在 20 年後的 1999 年：
我們認為，與普遍看法相反，在 RSA 密碼系統中沒有必要使用強素數。也就是說，通過使用強素數，與僅使用相同大小的“隨機”素數所獲得的安全性相比，安全性的提高可以忽略不計。
後一個參考文獻還包含一些關於生成強素數的方法及其預期性能的引用——誠然，對於數量級較小的數字，但該論文應該解釋為什麼每個人都可能已經失去了對該主題進行更多最新研究的動機. 具體來說，他們引用了 1984 年的約翰·戈登（其原始的排版使原始論文幾乎難以辨認），他們總結道：
尋找一個簡單的算法 $ k $ - 隨機測試位素數 $ k $ 素數的比特數因此需要時間 $ \Theta(k,T(k)) $ . 戈登的算法需要找到一個 $ k $ - 找到三個後的素數 $ k/2 $ -位素數，總時間為
$$ k,T(k) + 3(k/2),T(k/2) = 1.1875 (k,T(k)). $$ 這證明了 Gordon 的說法，即找到強素數只需要比尋找強素數的樸素算法多 19% 的工作量。
Gordon 的分析假設強素數在所有素數中的分佈沒有什麼特別之處。雖然這不是先驗的，但該分佈的任何有趣特性都可能是值得在數學期刊上發表的非凡結果，至少即使密碼學家不再關心。
在 GH Hardy 的優良傳統中，如何權衡實際密碼學家缺乏興趣與純數學家對數論中完全無用但困難的瑣事的興奮是我留給社會學家的問題。
找到大的強素數並不難。
原始RSA 文章建議，對於大的一些模糊定義，
- $ p $ 是一個大素數，
- $ p-1 $ 有一個很大的素因數 $ p^- $ （作為對Pollard 的 p-1因式分解的保護），
- 和 $ p^–1 $ 有一個很大的素因數 $ p^{–} $ （作為防止循環攻擊的保護）。
後來又補充說 $ p+1 $ 有一個很大的素因數 $ p^+ $ （作為對Williams 的 p+1因式分解的保護）和其他一些晦澀的標準（參見 Ronald L. Rivest 和 Robert D. Silverman 的Are Strong Primes Needed for RSA?）。
現代實踐（特別是 FIPS 186-4）只保留了大 $ p^- $ 和 $ p^+ $ ，或者完全放棄它們，因為它們沒有防範後來出現的通常更快的算法（ECM，GNFS ..）。看來這些大 $ p^- $ 和 $ p^+ $ 對於小於某個界限的素數，如 512 位或/和多素數 RSA，要求仍然是明智的，但只有當對手滿足於分解極多的公共模數之一時（這些要求並不能很好地保護一個特定的 RSA 密鑰，只有一個大組鍵）。
找到如此強的 RSA 素數比找到“正常”隨機素數需要更多的計算工作，但程式碼更複雜。一個基本的方法是先選擇 $ p^- $ 和 $ p^+ $ 隨機，所需數量級；然後搜尋奇數 $ p $ 和 $ p\equiv1\pmod{p^-} $ 和 $ p\equiv-1\pmod{p^+} $ . 使用中國剩餘定理找到第一個候選者，其他候選者的間隔為 $ 2,p^-,p^+ $ . 篩子可以有效地消除可被小素數整除的那些。