Priemgetaltest

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

Een priemgetaltest is een algoritme dat bepaalt of een gegeven getal al dan niet priem is. Een dergelijke test wordt onder andere gebruikt in de cryptografie. Het verschil tussen een priemgetaltest en ontbinding in priemfactoren is dat een priemgetaltest niet noodzakelijk priemfactoren geeft, maar alleen zegt of het gegeven getal wel of niet priem is. Ontbinding in priemfactoren geeft uiteraard wel deze factoren. Het is eenvoudiger om te bepalen of een getal wel of niet priem is (aan de hand van een priemgetaltest) dan wat de priemfactoren zijn. Sommige priemgetaltests bewijzen dat een getal priem is, terwijl andere bewijzen dat een getal samengesteld is. Deze tests zouden we daarom beter samengesteldheidstests kunnen noemen.

Naïeve methoden[bewerken]

De meest eenvoudige priemgetaltest is als volgt: Gegeven een positief geheel getal n, controleer of er een getal 2 ≤ mn−1 is zodat n deelbaar is door m. Als dit het geval is, dan is n samengesteld; anders is n priem. Merk op dat als n samengesteld is, we met deze test ook priemfactoren vinden. Hiermee is het ook een factorisatiemethode.

Het blijkt echter dat het niet nodig is om alle m tot en met n−1 te controleren, maar slechts tot en met \scriptstyle\sqrt{n}. De reden hiervoor is: als n samengesteld is, dan is n het product van twee factoren, waarvan een tenminste ≤\scriptstyle\sqrt{n} is.

Er kunnen zelfs nog meer getallen m worden overgeslagen. Als n namelijk niet deelbaar is door 2, dan is n ook niet deelbaar door 4, 6, 8, enz. Kortom, n is niet deelbaar door alle even getallen. Als n vervolgens niet deelbaar is door 3, dan is n ook niet deelbaar door alle veelvouden van drie. Dit voortzettend geeft de Zeef van Eratosthenes, waaruit volgt dat we alleen alle m tussen 2 en \scriptstyle\sqrt{n} hoeven te controleren met m priem.

Deze methodes kunnen versneld worden door van tevoren een lijst te maken met priemgetallen (bijvoorbeeld aan de hand van de Zeef van Eratosthenes) en te kijken of het te testen getal n deelbaar is door een van deze getallen. Als dit het geval is, is het getal samengesteld en hoeft men geen andere tests meer toe te passen.

Probabilistische tests[bewerken]

De meest gebruikte priemgetaltests zijn probabilistische tests. In deze tests worden naast het te testen getal n ook willekeurige getallen a gebruikt, waarbij aan het begin van de test wordt bepaald hoeveel verschillende a 's gekozen worden. In het algemeen geldt in probabilistische tests dat een getal dat werkelijk priem is ook als priem zal worden gemeld; een getal dat samengesteld is kan echter ook als priem worden gemeld. De kans op deze fout kan worden verkleind door de test te herhalen met verschillende waarden van a. Voor een aantal tests geldt dat voor elke samengestelde n tenminste de helft van alle a 's zal geven dat n inderdaad samengesteld is. Voor deze priemgetaltest geldt daarom: als er voor een geheel getal k, k tests worden uitgevoerd (met ook k verschillende a 's), dan is de kans dat n toch als priem wordt gemeld hoogstens 2k. Deze kans kunnen we verkleinen door k willekeurig groot te kiezen.

Een probabilistische test heeft in het algemeen de volgende structuur:

  1. Kies een willekeurig getal a.
  2. Controleer een bepaalde gelijkheid (afhankelijk van de gekozen test) betreffende het getal a en het te testen getal n. Als de gelijkheid niet geldt, dan is n samengesteld en heet a een getuige van het feit dat n samengesteld is. Er hoeft niet verder getest te worden.
  3. Herhaal vanaf stap 1 totdat er een bepaalde zekerheid van samengesteldheid is.

Als na een vooraf bepaald aantal iteraties (namelijk k) nog steeds niet is gevonden dat n samengesteld is, kan het waarschijnlijk priem worden verklaard.

Wanneer n een samengesteld getal is, dan zijn er de volgende twee mogelijkheden:

  • de test geeft uitvoer samengesteld voor een zekere a; in dit geval wordt a een getuige genoemd van het feit dat n samengesteld is;
  • de test geeft uitvoer waarschijnlijk priem voor een zekere a; in dit geval wordt a een leugenaar genoemd voor n.

Voorbeelden[bewerken]

De eenvoudigste probabilistische test is de priemtest van Fermat (dit is een van de tests die beter samengesteldheidstests zouden kunnen heten). Deze werkt als volgt:

Gegeven een geheel getal n, kies een willekeurig geheel getal a zodat ggd(a,n) = 1. Bereken an−1 modulo n. Als de uitkomst hiervan ongelijk is aan 1, dan is n samengesteld. Als de uitkomst 1 is, dan is n mogelijk priem.

De priemtest van Fermat is een heuristische test: sommige samengestelde getallen (Carmichaelgetallen) zullen als "mogelijk priem" worden verklaard ongeacht de gekozen getuige. Desalniettemin wordt deze test soms gebruikt als een getal snel gecontroleerd moet worden op primaliteit, bijvoorbeeld in het RSA encryptiealgoritme, bij het genereren van de sleutel.

De Miller-Rabin priemgetaltest en Solovay-Strassen priemgetaltest, ook voorbeelden van samengesteldheidstests, zijn iets geraffineerder en vinden alle samengestelde getallen: voor elk samengesteld getal n geldt voor de Miller-Rabin respectievelijk Solovay-Strassen test dat tenminste 3/4 respectievelijk 1/2 van de getallen a getuigen zijn van het feit dat n samengesteld is.

De Miller-Rabin test werkt als volgt: Gegeven een geheel getal n, kies een willekeurig geheel getal a < n. Als:

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

en

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

dan is n samengesteld en is a een getuige. Anders is n mogelijk priem.

De Solovay-Strassen test werkt vergelijkbaar: Gegeven een geheel getal n, kies een willekeurig getal a < n. Als:

\left( \frac{a}{n} \right) \pmod{n} \not\equiv a^{\frac{n-1}{2}} \ ,

met

\ \left( \frac{a}{n} \right) \ het Jacobi-symbool,

dan is n samengesteld en is a een getuige. Anders is n mogelijk priem.

Een ander voorbeeld is de Lucas-Lehmer test. Deze test vereist factorisatie van n−1; dit houdt in dat hij niet geschikt is voor de algemene doeleinden van een priemgetaltest, maar kan nuttig zijn als het te testen getal n een speciale vorm heeft, bijvoorbeeld Mersenne-getallen (zie Lucas-Lehmertest voor mersennegetallen).

De Lucas-Lehmer test gebruikt dat als n priem is, dat dan de multiplicatieve orde van een getal a (mod n) gelijk is aan n−1 als a een primitieve wortel modulo n is. Dus als we kunnen laten zien dat a een primitieve wortel is voor n, dan is n priem.

Deterministische methoden[bewerken]

De Miller-Rabin priemgetaltest is niet alleen een probabilistische methode, deze heeft ook een deterministische versie.[1] De oorspronkelijke versie van Miller was zelfs deterministisch, maar omdat deze afhangt van de nog onbewezen Riemann-hypothese, heeft Rabin de test aangepast tot een probabilistische methode.

In augustus 2002 brachten Manindra Agrawal, Neeraj Kayal en Nitin Saxena het artikel Primes is in P uit op het internet.[1] Hierin beschreven ze een nieuwe methode om primaliteit te testen. Deze methode is naar hen vernoemd en heet de AKS-test. Met deze methode is het mogelijk in polynomiale tijd te bepalen of een getal een priemgetal is.

Referenties[bewerken]

  1. a b Manindra Agrawal, Neeraj Kayal, Nitin Saxena, PRIMES is in P, Annals of Mathematics Vol. 160 (2004), No. 2, pp. 781–793.
  • Dit artikel of een eerdere versie ervan is (gedeeltelijk) vertaald vanaf de Engelstalige Wikipedia, die onder de licentie Creative Commons Naamsvermelding/Gelijk delen valt. Zie de bewerkingsgeschiedenis aldaar.
  • (en) Cai, Jin-Yi en Zhu, Hong, Progress in Computational Complexity Theory, Journal of Computational Science and Technology Vol. 20 (2005), No. 6, pp. 735-750.
  • (en) Agrawal, M. and Biswas, S., Primality and Identity Testing via Chinese Remaindering, Journal of the ACM Vol. 50 (2003), No. 4, pp.429-443.