Miller-Rabin-priemgetaltest

De Miller-Rabin-priemgetaltest of Rabin-Miller-priemgetaltest is een priemgetaltest: een algoritme dat bepaalt of een gegeven getal priem is of niet. Het is vergelijkbaar met de priemtest van Fermat en de Solovay-Strassen-priemgetaltest, die net als de Miller-Rabin-priemgetaltest veelal worden gebruikt in de cryptografie. De originele versie van deze test is gemaakt door Gary L. Miller en is deterministisch. Het deterministische deel van deze test is echter afhankelijk van de nog onbewezen Riemann-hypothese. Michael O. Rabin heeft de test veranderd tot een probabilistische test, die nergens van afhankelijk is en altijd werkt.

Theorie

Het principe van de Miller-Rabin-priemgetaltest is hetzelfde als dat van de Fermattest en de Solovay-Strassen-priemgetaltest: van een of meer eigenschappen van priemgetallen wordt nagegaan of het te testen getal deze eigenschap of eigenschappen heeft. Is dit niet het geval, dan is het getal geen priemgetal. Is het wel het geval, dan kan alleen geconcludeerd worden dat het getal mogelijk (waarschijnlijk) een priemgetal is.

Lemma

Het volgende lemma betreft vierkants-eenheidswortels in het eindige lichaam Z/pZ voor p een oneven priemgetal. Uiteraard geven 1 en −1 altijd 1 als ze modulo p worden gekwadrateerd; dit zijn de triviale vierkantswortels van 1 (mod p).

Het lemma luidt: er zijn geen niet-triviale vierkantswortels van 1 (mod p).

Bewijs

Stel

$x^{2}\equiv 1{\pmod {p}}$,

dan

$(x-1)(x+1)=x^{2}-1\equiv 0{\pmod {p}}.$

Dat houdt in dat $p$ een deler is van $x-1$ of van $x+1$. Daaruit volgt

$x-1\equiv 0{\pmod {p}},$ dus $x\equiv 1{\pmod {p}}$

of

$x+1\equiv 0{\pmod {p}},$ dus $x\equiv -1{\pmod {p}}.$

Het principe van de test

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

$a^{d}\equiv 1{\pmod {n}}$

ofwel dat

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

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

$a^{n}\equiv a{\pmod {n}}.$

Hieruit volgt ook:

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

Door herhaald worteltrekken uit $a^{n-1}$ is volgens het voorgaande lemma de uitkomst 1 of -1. Is de uitkomst -1, dan geldt kennelijk de tweede equivalentie en is het bewijs geleverd. Is de uitkomst alle $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 $a\in \{2,3,\ldots ,n-2\}$ gevonden wordt, waarvoor

$a^{d}\not \equiv 1{\pmod {n}}$

én

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

dan is $a$ een getuige van het feit dat $n$ samengesteld is. Anders is $n$ zeer waarschijnlijk priem met basis $a$. Is $n$ toch samengesteld, dan heet $a$ een leugenaar voor $n$.

Voor alle oneven samengestelde $n$ zijn er vele getuigen, maar er is geen eenvoudige manier bekend zo'n getuige te vinden. De oplossing is de test probabilistisch te maken: kies willekeurig een $a\in (\mathbb {Z} /n\mathbb {Z} )^{*}$, en ga na of het een getuige is van de samengesteldheid van $n$. Als $n$ samengesteld is, zullen de meeste keuzes getuige zijn van de samengesteldheid, en zal de test met grote waarschijnlijkheid dat ontdekken. Er blijft echter een kleine kans dat de gekozen $n$ een sterke leugenaar is voor $n$. De kans op zulke fouten kan verminderd worden door de test te herhalen voor meerdere onafhankelijk gekozen $a$.

Voorbeeld

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

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

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

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

Dus is voor een $r$ waarvoor geldt $0\leq r<s=2$ niet voldaan aan de gewenste equivalenties, zodat 174 geen getuige ervan is dat 221 samengesteld is. Dus is ofwel 221 priem, ofwel is 174 een leugenaar voor 221. Kies nog een andere $a$, bijvoorbeeld $a=137$. Bekijk weer de equivalenties:

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

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

$a^{s^{1}\cdot d}=137^{110}\equiv 205\not \equiv -1{\pmod {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 getest wordt voor primaliteit; 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 a we de test uitvoeren, des te nauwkeuriger is de test. Het is bewezen dat voor elk oneven samengesteld getal n, ten minste 3/4 van de bases a getuigen zijn van het feit dat n samengesteld is. Dus als n samengesteld is, dan verklaart de Miller-Rabin priemgetaltest n als waarschijnlijk priem met kans hoogstens 4^−k. In dit opzicht verheft deze test zich boven de Solovay-Strassen priemgetaltest, want die verklaart een samengesteld getal als waarschijnlijk priem met kans hoogstens 2^−k.

Externe links

• (en) Arnault, F., Rabin-Miller Primality test: Composite Numbers Which Pass It, Mathematics of Computation Vol. 64 (1995), No. 209, pp. 355-361.
• (en) Hurd, J., Verification of the Miller-Rabin probabilistic primality test, The Journal of Logic and Algebraic Programming Vol. 56 (2003), pp. 3-21.