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: we hebben een gelijkheid of een aantal gelijkheden waarvan we weten dat priemgetallen daar aan voldoen, en we kijken of het getal dat we willen testen op primaliteit daaraan voldoet.

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).

Het bewijs is als volgt: stel dat er wel een niet-triviale vierkantswortel is van 1 (mod p), noem deze x. Dan geldt:

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

We hadden aangenomen dat x niet-triviaal was, dus x is noch 1 (mod p) noch −1 (mod p). Hieruit volgt dat zowel x−1 als x + 1 relatief priem zijn met p. Dit heeft tot gevolg dat noch x−1 noch x + 1 deelbaar is door p. Echter, wegens de definitie van een priemgetal geldt dat als twee gehele getallen niet deelbaar zijn door p, dan is hun product ook niet deelbaar door p. Hieruit volgt dat:

(x-1)(x+1) \not\equiv 0 \pmod{p}.

Dit geeft een tegenspraak, waaruit volgt dat x niet niet-triviaal kan zijn.

Het principe van de test[bewerken]

Zij n een oneven priemgetal. Dan is n−1 even en kunnen we dit schrijven als 2s·d, met s en d positieve gehele getallen en d oneven. Voor elke a in (Z/nZ)* geldt ofwel

a^d\equiv 1 \pmod{n}

ofwel

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

Het bewijs is als volgt: herinner de Kleine stelling van Fermat:

a^n\equiv a\pmod{n},

die alleen geldt voor n priem, en schrijf dit om als:

a^{n-1}\equiv 1\pmod{n}.

Wegen het voorgaande lemma geldt, voor een geheel getal 0≤k≤s−1 het volgende:

 \text{als }
\left( a^{2^s \cdot d} \right)^{\left( \frac{1}{2}\right)^k} \equiv 1\pmod{n},\text{ dan } \left( a^{2^s\cdot d}\right)^{\left( \frac{1}{2}\right)^{k+1}} \equiv \pm 1\pmod{n}.

Dus als we de vierkantswortel trekken uit an−1, krijgen we 1 of −1. Als we 1 krijgen, dan blijven we vierkantswortels trekken totdat we −1 krijgen. Wanneer we −1 krijgen, voor een zekere k = l, dan:


a^{2^r \cdot d} \equiv \left( a^{2^s \cdot d} \right)^{\left( \frac{1}{2}\right)^l} \equiv -1\pmod{n},

waar r = sl; dus de tweede gelijkheid geldt en we zijn klaar. In het andere geval, wanneer we alle machten van 2 eruit gehaald hebben en de tweede gelijkheid geldt nog steeds niet, dan houden we over  a^d \pmod{n}, wat ook gelijk moet zijn aan 1 of −1, aangezien het ook een vierkantswortel is. Merk echter op dat aangezien de tweede gelijkheid nooit gold, het ook niet gold voor r = 0; dit houdt in dat:

a^{2^0\cdot d}=a^d\not\equiv -1\pmod{n}.

Oftewel, als de tweede equivalentie niet geldt, dan geldt de eerste.

De Miller-Rabin priemgetaltest is gebaseerd op de contrapositie van het bovenstaande: Als we een a kunnen vinden zodat

 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 waarschijnlijk priem met basis a; in dit geval kan n ofwel priem zijn, ofwel samengesteld en heet a een leugenaar voor n. De term leugenaar komt van het feit dat n in dit geval samengesteld is, maar toch aan de gelijkheden voldoet, alsof het een priemgetal zou zijn.

Voor n een samengesteld getal zijn er veel getuigen a. Het is echter niet eenvoudig te achterhalen voor welke a dit het geval is. Om toch te ontdekken dat n samengesteld is, maken we de test probabilistisch: kies a in (Z/nZ)* willekeurig en controleer of het wel of geen getuige is van het feit dat n samengesteld is. Als n samengesteld is, dan zullen de meeste van deze a 's getuigen zijn, en er is een grote kans dat de test n als samengesteld zal melden. Er is echter nog een kleine kans dat we ongelukkig een a kiezen die een leugenaar is voor n. We kunnen deze kans verkleinen door de test voor verschillende a 's te herhalen.

Voorbeeld[bewerken]

Stel dat we het getal n = 221 willen testen op primaliteit. Schrijf n−1 = 220 = 22·55 (dus s = 2 en d = 55). Kies een willekeurige a < n, bijvoorbeeld a = 174. We bekijken de gelijkheden voor deze waarde van a:

  • ad (mod n) = 17455 (mod 221) = 47 ≠ 1
  • a20·d (mod n) = 17455 (mod 221) = 47 ≠ n−1
  • a21·d (mod n) = 174110 (mod 221) = 220 = n−1.

Aangezien 220 ≡ −1 (mod n) geldt ofwel dat 221 priem is, ofwel dat 174 een leugenaar is voor 221. Kies nog een willekeurige a, bijvoorbeeld a = 137. Bekijk weer de gelijkheden:

  • ad (mod n) = 13755 (mod 221) = 188 ≠ 1
  • a20·d (mod n) = 13755 (mod 221) = 188 ≠ n−1
  • a21·d (mod n) = 137110 (mod 221) = 205 ≠ n−1.

Hieruit volgt dat 137 een getuige is voor het feit dat 221 samengesteld is, en 174 was inderdaad een leugenaar. Merk op dat we nu 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.