算法原理:
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 可以正确识别