Algoritmprincip:
Miller-Rabin är ett probabilistiskt primtalstest baserat på en utvidgning av Fermats lilla sats. För ett udda tal n, skriv n-1 som 2^r × d, testa sedan om det uppfyller:
a^d ≡ 1 (mod n) 或 a^(2^i × d) ≡ -1 (mod n) 对某个 0 ≤ i < r
Antal testomgångar och noggrannhet:
- Probabilistisk testning:Välj slumpmässigt en bas a; varje testomgång minskar felfrekvensen till 1/4
- k omgångar testning:Teoretisk felfrekvens ≤ (1/4)^k, faktisk felfrekvens är mycket lägre
- Deterministisk testning:För n < 3 317 044 064 679 887 385 961 981, med basuppsättningen {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37} fås 100% noggranna resultat
Specialfall:
- Små primtal:Tal som 2, 3, 5, 7 identifieras direkt
- Jämna tal:Alla jämna tal utom 2 är sammansatta
- Carmichael-tal:Tal som klarar Fermats test men är sammansatta (t.ex. 561) kan korrekt identifieras av Miller-Rabin