如何測試像米勒拉賓這樣的素數測試的實現？
Miller-Rabin素數檢驗是一種檢查數字是否為素數的算法。測試這種算法的實現（或一般的任何素數測試）的最佳方法是什麼？
好吧，顯而易見的事情是給它一長串已知素數的整數，並查看算法是否正確報告它（它偶爾將復合報告為“相對素數”而不被視為錯誤，只要它至少在 75% 的情況下將該值報告為複合值）。
但是，這種簡單的測試可能會遺漏一些東西。Miller-Rabin 測試可以報告 $ n $ 是“複合的”，因為以下兩個原因之一：
- 因為 $ g^{n-1} \ne 1 \bmod n $ ; 也就是說，費馬檢驗失敗
- 因為 $ g^{(n-1)/2^\ell} \bmod n $ 是一個非平凡平方根
如果你只是扔隨機複合材料 $ n $ 在那裡，它幾乎總是會遇到第一個原因。因此，故意嘗試一個值是有意義的 $ n $ 第二個原因失敗了。
一組值 $ n $ 被稱為卡邁克爾數；這些是與 $ g^{n-1} = 1 \bmod n $ 對於所有整數 $ g $ 相對於 $ n $ ; 如果我們用不小的因子來檢驗卡邁克爾數，費馬檢驗幾乎總是會成功，所以如果檢驗失敗，那將是第二個原因。
找到這樣的卡邁克爾數的一種方法是搜尋素數三元組 $ 6p+1, 12p+1, 18p+1 $ ; 如果三個都是素數，那麼 $ (6p+1)(12p+1)(18p+1) $ 是卡邁克爾數。
找到其他進行測試的軟體，然後比較前 10^10 或更多整數，然後比較隨機大數（都在 64 位範圍內，假設您的軟體這樣做，則要大得多）。嘗試各種基地。
使用所有 64 位以 2 為底的強偽素數的 Feitsma-Galway 數據庫，並確保為所有這些數字生成相似的結果（這些數字通過了以 2 為底的 MR 測試）。當然，您只想執行這些數字並看到它們都通過了基數 2——而不是嘗試執行所有小於 2^64 的複合！
為一些結合鹼基的 OEIS 序列（例如 A056915）編寫一個簡單的測試，看看您是否生成了相同的初始項。
使用一些通過許多鹼基的測試偽素數（範例）。這包括通過所有小於 53、67、71、73、101、307、547、877、1009 的鹼基。驗證它通過了所有鹼基，然後驗證它沒有通過該鹼基。
出於比較的目的，您可以找到另一個使用相同語言的程序並編寫一個小測試腳本來呼叫這兩個函式並進行比較。我曾經使用許多其他模組為我的 Perl 軟體重新執行過它，並且偶爾會重新執行它。您還可以（希望很少）在其他已發布程式碼中發現錯誤——理想情況下，您可以送出帶有更新檔的錯誤報告。
您也可以寫出答案並通過 md5sum 或類似方式發送，或者執行您自己的校驗和常式。然後使用其他軟體並執行相同的操作。這不是很有效，也不是很容易生成隨機輸入，但可以讓您與幾乎任何其他軟體進行比較。
正如其他人所指出的，在解釋上存在一些差異。例如，測試不是在偶數上定義的。一些軟體只是忽略了這一點，因此會對一些偶數（！）報告為真，而其他軟體對偶數進行快速預測試（對 2 返回真，對所有其他偶數返回假）。另一個問題是如何處理大於輸入的基數和是輸入的倍數的基數。在考慮某些確定性基集時，這些尤其重要。
素性測試
上一節專門針對 Miller-Rabin 實現，例如 mr(n,base)。測試完整的素數測試有點困難。當測試異常緩慢時會變得非常困難，例如許多 AKS 實現如果需要幾分鐘或幾小時來執行每個微小的輸入，則幾乎沒有完成測試。
- 分別測試各個組件。這包括 MR、Lucas、預測試等。確保這些部分都能正常工作。對於像 AKS 這樣的多步算法，確保每一步都在做正確的事情（我發現一個有循環錯誤，所以它只是進行了試驗劃分，從未執行過實際測試）。
- 如果可能，與其他人一起進行程式碼審查。對於開源來說，這很難得到。
- 對於小輸入，與已知輸入或其他一些軟體進行比較。我有一些測試，使用其他人編寫的其他篩選模組來有效地生成素數列表，然後通過它驗證我的程式碼是否為每個素數返回真，為每個複合物返回假。IMO 重要的是，此輸入來自完全不同的來源，而不是您編寫的內容。
- 所有 64 位輸入都有簡單的確定性測試。對於 isprime() 函式，現在沒有理由讓它成為機率。當然，對於較大的輸入，我們通常不使用確定性測試，因為需要時間和編碼（好的測試比大多數人意識到的要快得多，但仍然比 BPSW 慢得多）。
- 編寫一個工具，生成您選擇的大小（例如 1024 位）的隨機數，並通過其他人的系統和您的系統發送它們，驗證結果是否匹配。讓它在一夜之間執行。
- 如果是為了 Crypto，你真的應該讓有經驗的人仔細審查它。即便如此，你也不得不擔心它仍然會錯過一些重要的事情。如果你沒有這個瑣碎的疑問，也許你不應該編寫加密軟體……儘管我們都喜歡這樣做，但一般建議是“不要編寫自己的加密軟體”是有原因的。