最有效的算法來產生一個位範圍內的隨機素數

Question

NTL/ZZ.h有一個函數可以爲您產生一個Random Prime ZZ數字（ZZ RandomPrime_ZZ（long，long）），我想知道您是否有人知道NTL使用哪種算法來實現這一點。否則，請推薦一個你知道的高效算法。 「在一系列比特中」，我的意思是根據參數（例如2048比特）產生x比特的素數。

Answer 1

NTL（截至版本9.20，至少）生成具有適當位長度的隨機奇數，並使用給定數量的Miller-Rabin測試（默認爲10）進行測試。如果他們被測試爲複合，則重新開始，否則返回（可能素數）。

GenPrime做同樣的事情，但不是給它一些測試，而是給它一個數字，指出你願意接受的最大失敗概率（默認值是80，意味着它可能會失敗到每2^80≈10^ 24平均嘗試次數，它使用Damgård，Landrock，& Pomerance（1993）的深層結果來計算所需的測試次數