如何有效地生成給定長度的隨機安全素數？

一個素數 $ p $ 據說是安全素數，如果 $ (p-1)/2 $ 也是素數。如何有效地生成安全素數？我在 sagemath 中編寫了以下程式碼，它生成 1536 位的隨機安全素數。這段程式碼用了 426 秒來生成一個安全的素數。這是非常低效的。有沒有更快的方法來有效地生成安全素數？

while True:
   p = random_prime(2^1536-1, false, 2^(1535))
   if ZZ((p-1)/2).is_prime():
       return p

沒有比生成安全素數更有效的方法了。即使在 OpenSSL 的優化程式碼中，生成安全素數也可能需要很長時間（30 秒、1 分鐘、2 分鐘）。在你的電腦上執行“openssl gendh 1024”看看（在我的 2015 MacBook Pro 上可能需要很長時間，但差異真的很大，所以多試幾次）。

評論討論了 RSA 的安全素數。實際上， RSA 不需要安全素數。但是，它們是為有限域密碼術（有限域上的 Diffie-Hellman）生成參數以及密碼學中的其他應用所必需的。例如，零知識範圍證明使用具有未知順序的組，這由 RSA 模數和對該模數的 Pedersen 承諾定義。當使用安全素數時，這可以確保群很大，而且隨機群元素是具有壓倒性機率的生成器。有關此特定應用程序的更多資訊，請參閱Set Membership and Range Proofs的有效協議的第 1.2 節。

因此，在更高級的密碼學中，有很多安全素數的應用（事實上，RSA 加密不是其中之一）。

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