Algorithm Principle:
Miller-Rabin is a probabilistic primality test based on an extension of Fermat's little theorem. For an odd number n, write n-1 as 2^r × d, then test whether it satisfies:
a^d ≡ 1 (mod n) 或 a^(2^i × d) ≡ -1 (mod n) 对某个 0 ≤ i < r
Number of test rounds and accuracy:
- Probabilistic Testing:Randomly select a base a; each test round reduces the error rate to 1/4
- k rounds of testing:Theoretical error rate ≤ (1/4)^k, actual error rate is much lower
- Deterministic Testing:For n < 3,317,044,064,679,887,385,961,981, using the specific base set {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37} yields 100% accurate results
Special Cases:
- Small Primes:Numbers like 2, 3, 5, 7 are directly identified
- Even Numbers:All even numbers except 2 are composite
- Carmichael Numbers:Numbers that pass the Fermat test but are actually composite (e.g., 561) can be correctly identified by Miller-Rabin