演算法原理:
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 可以正確識別