Python 的 pycrypto 庫如何生成素數？

Python 中的 pycrypto 庫可以生成隨機的 n 位素數。我使用的語法如下：

from Crypto.Util import number
number.getPrime(2048)

上面的函式具有非常令人印象深刻的性能，並以非常小的延遲返回素數。在這個函式中，在如此短的時間內生成如此大的素數的過程是什麼？

文件沒有直接告訴實現的算法。可以從源程式碼中查看。getPrime使用isPrime並呼叫Rabin-Miller Primality test。

• getPrime生成一個隨機奇數 $ \texttt{N} $ 並打電話isPrime

number=getRandomNBitInteger(N, randfunc) | 1
    while (not isPrime(number, randfunc=randfunc)):
        number=number+2

• isPrime首先檢查均勻度和預先計算的 Sieve 素數，該列表是前 10000 個素數。它可能是 Sieve 中的素數或可被其中一個整除。如果都不是，則執行 Rabin-Miller 測試。

**機率：**的返回值getPrime，如果是可能的素數，則機率由下式給出 $$ 1 - \frac{1}{4^k} $$在哪裡 $ k $ 是迭代次數。

**迭代次數：**庫定義

false_positive_prob=1e-6

計算 $ k $ 經過

k = int(math.ceil(-math.log(false_positive_prob)/math.log(4)))

由此，庫中的迭代次數為 $ k=10 $ .

請注意，在我的本科階段，我們使用 $ k=20 $ . 1e-12在圖書館擁有的最壞情況下，這會導致誤報1e-6。

**複雜性：**如果使用重複平方的模冪運算，那麼複雜性是 $ \mathcal{O}(k \log^3 n) $ 在哪裡 $ k $ 是確定機率的要測試的迭代次數。

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