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 ${\displaystyle {\text{mod}}\ p}$, dus in ${\displaystyle \mathbb {Z} /p\mathbb {Z} }$, geen andere getallen dan 1 en −1 die in het kwadraat gelijk aan 1 zijn.

Principe van de test

Zij ${\displaystyle n>2}$ een priemgetal. Dan is ${\displaystyle n-1}$ even, zeg ${\displaystyle n-1=2^{s}d}$, met ${\displaystyle s}$ en ${\displaystyle d}$ positieve gehele getallen en ${\displaystyle d}$ oneven. Voor elke ${\displaystyle a\in \mathbb {Z} /n\mathbb {Z} }$ geldt ofwel dat

${\displaystyle a^{d}\equiv 1\mod {n}}$

ofwel dat

${\displaystyle a^{2^{r}\cdot d}\equiv -1\mod {n}}$ voor een zekere ${\displaystyle 0\leq r\leq s-1}$.

Zij namelijk ${\displaystyle a\in \{2,3,\ldots ,n-2\}}$, dan geldt volgens de kleine stelling van Fermat als ${\displaystyle n}$ een priemgetal is:

${\displaystyle a^{n}\equiv a\mod {n}}$

Hieruit volgt ook:

${\displaystyle a^{n-1}=a^{2^{s}d}\equiv 1\mod {n}.}$

Door herhaald worteltrekken uit ${\displaystyle a^{n-1}}$ 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 ${\displaystyle s}$ 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 ${\displaystyle a\in \{2,3,\ldots ,n-2\}}$ wordt gevonden, waarvoor

${\displaystyle a^{d}\not \equiv 1\mod {n}}$

en

${\displaystyle a^{2^{r}\cdot d}\not \equiv -1\mod {n}}$ voor alle ${\displaystyle 0\leq r\leq s-1}$,

dan betekent dat dat ${\displaystyle n}$ een samengesteld getal is. ${\displaystyle a}$ heet er een getuige van dat ${\displaystyle n}$ samengesteld is. Anders is ${\displaystyle n}$ zeer waarschijnlijk een priemgetal met basis ${\displaystyle a}$. Is ${\displaystyle n}$ toch samengesteld, dan heet ${\displaystyle a}$ een leugenaar voor ${\displaystyle n}$.

Voor alle oneven samengestelde ${\displaystyle n}$ 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 ${\displaystyle a\in \mathbb {Z} /n\mathbb {Z} }$ en ga na of het een getuige is van de samengesteldheid van ${\displaystyle n}$. Als ${\displaystyle n}$ 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 ${\displaystyle n}$ een sterke leugenaar is voor ${\displaystyle n}$. De kans op zulke fouten kan worden verminderd door de test te herhalen voor verschillende onafhankelijk gekozen ${\displaystyle a}$.

Voorbeeld

Stel dat het getal ${\displaystyle n=221}$ getest wordt op primaliteit. Schrijf ${\displaystyle n-1=220=2^{2}\times 55}$, dus ${\displaystyle s=2}$ en ${\displaystyle d=55}$. Kies een willekeurige ${\displaystyle a<n}$, bijvoorbeeld ${\displaystyle a=174}$ en bekijk de equivalenties:

${\displaystyle a^{d}=174^{55}\equiv 47\not \equiv 1\mod {221}}$

${\displaystyle a^{s^{0}\cdot d}=174^{55}\equiv 47\not \equiv -1\mod {221}}$

${\displaystyle a^{s^{1}\cdot d}=174^{110}\equiv 220\equiv -1\mod {221}}$

Dus is voor een ${\displaystyle r}$ waarvoor geldt ${\displaystyle 0\leq r<s=2}$ 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 ${\displaystyle a}$, bijvoorbeeld ${\displaystyle a=137}$. Bekijk weer de equivalenties:

${\displaystyle a^{d}=137^{55}\equiv 188\not \equiv 1\mod {221}}$

${\displaystyle a^{s^{0}\cdot d}=137^{55}\equiv 188\not \equiv -1\mod {221}}$

${\displaystyle a^{s^{1}\cdot d}=137^{110}\equiv 205\not \equiv -1\mod {221}}$

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 ${\displaystyle a}$ de test wordt uitgevoerd, hoe nauwkeuriger de test is. Het is bewezen^[1] dat voor ieder oneven samengestelde getal ${\displaystyle n}$ ten minste 3/4 van de bases ${\displaystyle a}$ getuigen zijn van het feit dat ${\displaystyle n}$ samengesteld is. Dus als ${\displaystyle n}$ samengesteld is noemt de Miller-Rabin-priemgetaltest ${\displaystyle n}$ waarschijnlijk een priemgetal met een kans van hoogstens ${\displaystyle 4^{-k}}$. 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 ${\displaystyle 2^{-k}}$.