Rabin-Miller 強偽素數檢驗

一種素性檢驗，它提供了一種有效的機率演算法，用於確定給定數字是否為素數。它基於強偽素數的性質。

該演算法的步驟如下。給定一個奇數整數 ，令 ，其中 為奇數。然後選擇一個隨機整數 ，其中 。如果 或對於某個 ，，則 透過測試。一個素數將對所有 透過測試。

該測試非常快速，並且需要不超過 次乘法運算（模 ），其中 lg 是以 2 為底的對數。不幸的是，一個透過測試的數字不一定是素數。Monier (1980) 和 Rabin (1980) 已經證明，對於最多 1/4 的可能基數 ，合數會透過測試。如果對一個合數執行 次獨立的測試，那麼它透過每次測試的機率為 或更小。

然而，如果預先知道透過特定測試集的最小合數，那麼該測試集就構成了對所有較小數的素性證明。使用前 個素數進行多次 Rabin-Miller 測試時，透過測試的最小奇數序列（對於 , 2, ...）由 2047, 1373653, 25326001, 3215031751, 2152302898747, 3474749660383, 341550071728321, 341550071728321, ... 給出 (OEIS A014233; Jaeschke 1993)。因此，使用前 7 個素數（使用 8 個素數沒有改進）的多次 Rabin 測試對於高達 的每個數字都是有效的。

Wolfram 語言在基數 2 和 3 中結合 Lucas 偽素數測試實現了多次 Rabin-Miller 測試，作為函式使用的素性檢驗PrimeQ[n]。截至 1997 年，已知此過程僅對所有 是正確的，但沒有已知的反例，如果存在任何反例，預計它們出現的機率極小（即，遠小於計算機執行測試時發生硬體錯誤的機率）。