Algoritmeprincipe:
Miller-Rabin is een probabilistische priemgetaltest gebaseerd op een uitbreiding van de kleine stelling van Fermat. Voor een oneven getal n, schrijf n-1 als 2^r × d, en test vervolgens of het voldoet aan:
a^d ≡ 1 (mod n) 或 a^(2^i × d) ≡ -1 (mod n) 对某个 0 ≤ i < r
Aantal testrondes en nauwkeurigheid:
- Probabilistisch testen:Kies willekeurig een basis a; elke testronde verlaagt het foutpercentage tot 1/4
- k rondes testen:Theoretisch foutpercentage ≤ (1/4)^k, werkelijk foutpercentage is veel lager
- Deterministisch testen:Voor n < 3.317.044.064.679.887.385.961.981, met de specifieke basis set {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37} levert 100% nauwkeurige resultaten op
Speciale gevallen:
- Kleine priemgetallen:Getallen zoals 2, 3, 5, 7 worden direct geïdentificeerd
- Even getallen:Alle even getallen behalve 2 zijn samengesteld
- Carmichael-getallen:Getallen die de Fermat-test doorstaan maar eigenlijk samengesteld zijn (bijv. 561) kunnen correct worden geïdentificeerd door Miller-Rabin