尋找強質數
維基百科列出了質數強的以下條件：
$ p-1 $ 有很大的素因數。那是， $ p = a_1 q_1 + 1 $ 對於某個整數 $ a_1 $ 和大素數 $ q_1 $ .
$ q_1-1 $ 有很大的素因數。那是， $ q_1 = a_2 q_2 + 1 $ 對於某個整數 $ a_2 $ 和大素數 $ q_2 $ .
$ p+1 $ 有很大的素因數。那是， $ p = a_3 q_3 - 1 $ 對於某個整數 $ a_3 $ 和大素數 $ q_3 $ .
這對我來說似乎很模糊。“大素數”是什麼意思？應該多大 $ p_1 $ 相比較 $ p $ ?
而且，最重要的是，生成大的強素數或檢查大素數是否強的標準方法是什麼？此外，正在使用安全素數（形式為 $ p = 2*q + 1 $ ， 在哪裡 $ q $ 素數）安全和/或有效嗎？
問題中討論的所有屬性都適用於強素數 $ p $ 在使用的上下文中 $ p $ 作為大型複合材料的秘密因素 $ n $ 哪種分解應該是難以處理的；這些屬性在具有里程碑意義的RSA 論文(1978) 中給出，沒有任何理由。其他密碼系統中使用的（通常是公共的）素數的屬性可能不同。
第一個屬性
$ p-1 $ 有很大的素因數。那是， $ p = a_1 q_1 + 1 $ 對於某個整數 $ a_1 $ 和大素數 $ q_1 $ .
旨在使因式分解 $ n $ 很難使用Polard 的 p-1算法；這在某種程度上是相關的，因為該算法的成本部分與最高因子成正比 $ p-1 $ ， 在哪裡 $ p $ 是因素 $ n $ 算法表現出來的。
同樣，第三個屬性
$ p+1 $ 有很大的素因數。那是， $ p = a_3 q_3 - 1 $ 對於某個整數 $ a_3 $ 和大素數 $ q_3 $ .
旨在使因式分解 $ n $ 使用Williams的p+1算法很難；這在某種程度上是相關的，因為該算法的成本部分與最高因子成正比 $ p+1 $ ， 在哪裡 $ p $ 是因素 $ n $ 算法表現出來的。
考慮到上述情況的一項標準是FIPS 186-4（附錄 B.3），其中 $ q_1 $ 和 $ q_3 $ 需要大於 100 位時 $ p $ 是 512 位（並且可選： $ q_1 $ 和 $ q_3 $ 大於 140 或 170 位時 $ p $ 是 1024 或 1536 位）。很難定量地判斷何時對這些屬性採取預防措施（超出標準的一致性）是真正有意義的：在生成一些至少 1024 位的雙因素 RSA 密鑰時是沒有意義的；當生成非常多的具有相對較小因子的 RSA 模數（例如在多素數 RSA 中）時，它可能很有用，並且對手將受益於找到任何模數（而不是特定模數）的因式分解；看到這個問題及其答案。
第二個屬性
$ q_1-1 $ 有很大的素因數。那是， $ q_1 = a_2 q_2 + 1 $ 對於某個整數 $ a_2 $ 和大素數 $ q_2 $ .
與降低 RSA 循環攻擊成功的機率有關；看到這個答案。我沒有找到關於多大的定量評估 $ q_2 $ 應該是，或任何具有此要求的現代標準。我接受這樣的共識，即 RSA 循環攻擊對於實際密鑰大小的成功機率可以忽略不計（但非常感謝定量論證！）。
生成大的強素數的標準方法 $ p $ 具有第一個和第三個屬性（如果需要，可能是第二個）是選擇輔助素數 $ q_2 $ （如果需要）那麼 $ q_1 $ ， 和 $ q_3 $ ，然後生成 $ p $ ; 而不是選擇 $ p $ ，然後試圖展示 $ q_1 $ （然後 $ q_2 $ 如果需要）和 $ q_3 $ . 後一種方法的計算量非常大：如果 $ p $ 是一個隨機的 512 位素數，它需要分解 $ (p-1)/2 $ 和 $ (p+1)/2 $ ，它們大多是隨機的 511 位整數，這通常是一項艱鉅的工作。前一種方法（在實踐中使用）引入了顯著的複雜性，但計算負擔相對較小；上述 FIPS 186-4 附錄 B.3 中詳細介紹了幾種此類方法。