Miller-Rabin-priemgetaltest

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

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[bewerken]

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) en priemgetal is.

Lemma[bewerken]

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

,

dan

Dat houdt in dat een deler is van of van . Daaruit volgt

dus

of

dus

Het principe van de test[bewerken]

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 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 keren steeds 1, dan blijft de eerste equivalentie over.

Test[bewerken]

De Miller-Rabin-priemgetaltest is gebaseerd op de contrapositie van het bovenstaande: Als er een gevonden wordt, waarvoor

én

voor alle

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

Voor alle oneven samengestelde 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 </math>, en ga na of het een getuige is van de samengesteldheid van . Als 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 een sterke leugenaar is voor . De kans op zulke fouten kan verminderd worden door de test te herhalen voor meerdere onafhankelijk gekozen .

Voorbeeld[bewerken]

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

Dus is niet voor alle 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 , 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[bewerken]

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 ≤ an−2 willekeurig
      xad mod n
      x = 1 of x = n−1 dan doe de volgende LOOP
      voor r = 1,...,s−1
         xx2 mod n
         x = 1 dan uitvoer samengesteld
         x = n−1 dan doe de volgende LOOP
   uitvoer samengesteld
uitvoer waarschijnlijk priem

Nauwkeurigheid[bewerken]

Zoals gezegd: voor hoe meer getallen a we de test uitvoeren, des te nauwkeuriger is de test. Het is bewezen[1] 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 4k. In dit opzicht verheft deze test zich boven de Solovay-Strassen priemgetaltest, want die verklaart een samengesteld getal als waarschijnlijk priem met kans hoogstens 2k.

Referenties[bewerken]

  1. (en) Artikel van Bornemann

Externe links[bewerken]

  • (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.