素數判定器(Miller-Rabin)

數字輸入

示例數字:

檢測結果

輸入數字後點擊"開始檢測"

Miller-Rabin 演算法說明:

演算法原理: Miller-Rabin 是一種機率性素數判定演算法,基於費馬小定理的推廣。對於奇數 n,將 n-1 寫成 2^r × d 的形式,然後測試是否滿足:
a^d ≡ 1 (mod n) 或 a^(2^i × d) ≡ -1 (mod n) 对某个 0 ≤ i < r
測試輪數與準確性:
  • 機率性測試:隨機選擇底數 a,每輪測試將錯誤率降低到 1/4
  • k 輪測試:理論錯誤率 ≤ (1/4)^k,實際遠低於此
  • 確定性測試:對於 n < 3,317,044,064,679,887,385,961,981,使用特定底數集合 {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37} 可得到 100% 準確結果
特殊情況:
  • 小素數:2, 3, 5, 7 等直接判定
  • 偶數:除 2 外均為合數
  • Carmichael 數:能通過費馬測試但實際是合數的數字(如 561),Miller-Rabin 可以正確識別

應用場景:

  • 密碼學:RSA 金鑰生成時需要快速判定大素數
  • 數論研究:梅森素數、雙素數、孿生素數等的搜尋
  • 競賽程式設計:快速判定素數,時間複雜度 O(k log³n)
  • 隨機數生成:生成符合特定條件的大素數