Miller-Rabin-priemgetaltest
De Miller-Rabin-priemgetaltest of Rabin-Miller-priemgetaltest is een priemgetaltest, dus een algoritme dat bepaalt of een gegeven getal een priemgetal is of niet. Deze test kan met de priemtest van Fermat en de Solovay-Strassen-priemgetaltest worden vergeleken, die net als de Miller-Rabin-priemgetaltest vaak in de cryptografie worden gebruikt. De originele versie van deze test is door Gary Miller gemaakt en is deterministisch. Het deterministische deel van deze test is afhankelijk van de riemann-hypothese, maar die is nog niet bewezen. Michael Rabin heeft de test in een probabilistische test veranderd, die nergens van afhankelijk is en altijd werkt.

Theorie 
Het principe van de Miller-Rabin-priemgetaltest is hetzelfde als dat van de priemtest van Fermat en de Solovay-Strassen-priemgetaltest: van een of meer eigenschappen van priemgetallen wordt nagegaan of het te controleren getal die heeft. Is dit niet het geval, dan is het getal geen priemgetal. Is het wel het geval, dan kan alleen worden geconcludeerd dat het getal waarschijnlijk een priemgetal is.

Hulpstelling 
Hulpstelling: er zijn , dus in , geen andere getallen dan 1 en −1 die in het kwadraat gelijk aan 1 zijn.

Principe van de test 
Zij  een priemgetal. Dan is  even, zeg , met  en  positieve gehele getallen en  oneven. Voor elke  geldt ofwel dat
 
ofwel dat
  voor een zekere .

Zij namelijk , dan geldt volgens de kleine stelling van Fermat als  een priemgetal is:
 

Hieruit volgt ook:

Door herhaald worteltrekken uit  is volgens de voorgaande hulpstelling de uitkomst 1 of -1. Is de uitkomst -1, dan geldt kennelijk de tweede equivalentie en is het bewijs geleverd. Is de uitkomst alle  keren steeds 1, dan blijft de eerste equivalentie over.

Test 
De Miller-Rabin-priemgetaltest is gebaseerd op de contrapositie van het bovenstaande: Als er een  wordt gevonden, waarvoor
 
en
  voor alle ,
dan betekent dat dat  een samengesteld getal is.  heet er een getuige van dat  samengesteld is. Anders is  zeer waarschijnlijk een priemgetal met basis . Is  toch samengesteld, dan heet  een leugenaar voor . 

Voor alle oneven samengestelde  zijn er veel getuigen, maar er is geen eenvoudige manier bekend zo'n getuige te vinden. De oplossing is de test probabilistisch te maken: kies willekeurig een  en ga na of het een getuige is van de samengesteldheid van . Als  samengesteld is, zullen de meeste keuzes daar getuige van zijn en ontdekt de test dat met grote waarschijnlijkheid. Er blijft een kleine kans dat de gekozen  een sterke leugenaar is voor . De kans op zulke fouten kan worden verminderd door de test te herhalen voor verschillende onafhankelijk gekozen .

Voorbeeld 
Stel dat het getal  getest wordt op primaliteit. Schrijf , dus  en . Kies een willekeurige , bijvoorbeeld  en bekijk de equivalenties:
 
 
 

Dus is voor een  waarvoor geldt  niet voldaan aan de gewenste equivalenties, zodat 174 er geen getuige van is dat 221 samengesteld is. Dus is ofwel 221 priem, ofwel is 174 een leugenaar voor 221. Kies nog een andere , bijvoorbeeld . Bekijk weer de equivalenties:

 
 
 

Dus is 137 getuige voor het feit dat 221 samengesteld is, en 174 was inderdaad een leugenaar. Merk op dat we nog niets weten over de factoren van 221, namelijk 13 en 17.

Algoritme 
Het algoritme kan in pseudocode als volgt worden beschreven:
 Invoer:
     n > 2, een oneven geheel getal dat wordt gecontroleerd dat het een priemgetal is
     k, een geheel getal dat de nauwkeurigheid van de test bepaalt
 Uitvoer: samengesteld als n samengesteld is, anders waarschijnlijk priem
    schrijf n−1 als 2s·d met d oneven door machten van 2 uit n−1 weg te delen
    LOOP: herhaal k keer:
       kies 2 ≤ a ≤ n−2 willekeurig
       x ← ad mod n
       x = 1 of x = n−1 dan doe de volgende LOOP
       voor r = 1,...,s−1
          x ← x2 mod n
          x = 1 dan uitvoer samengesteld
          x = n−1 dan doe de volgende LOOP
    uitvoer samengesteld
 uitvoer waarschijnlijk priem

Nauwkeurigheid 
Zoals gezegd: voor hoe meer getallen  de test wordt uitgevoerd, hoe nauwkeuriger de test is. Het is bewezen dat voor ieder oneven samengestelde getal  ten minste 3/4 van de bases  getuigen zijn van het feit dat  samengesteld is. Dus als  samengesteld is noemt de Miller-Rabin-priemgetaltest  waarschijnlijk een priemgetal met een kans van hoogstens . In dit opzicht doet deze test het beter dan de Solovay-Strassen priemgetaltest, want die noemt een samengesteld getal als waarschijnlijk een priemgetal met een kans van hoogstens .

Algoritme
Priemgetaltest