Priemgetaltest

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

De zeef van Eratosthenes is de meest eenvoudige priemgetaltest: Gegeven een positief geheel getal $n$, controleer of er een getal $2\leq m\leq {\sqrt {n\ }}$ is zodat $n$ door $m$ kan worden gedeeld. Als dit het geval is, dan is $n$ samengesteld, anders is $n$ een priemgetal. Merk op dat als $n$ samengesteld is, we met deze test ook priemfactoren vinden. Hiermee is het ook een methode om een getal in priemfactoren te ontbinden. Er moet alleen tot en met ${\sqrt {n\ }}$ worden gecontroleerd, omdat als $n$ samengesteld is, $n$ het product van twee factoren is, waarvan er een ten minste $\leq {\sqrt {n\ }}$ is. Alle even getallen kunnen ook worden overgeslagen, omdat die door twee kunnen worden gedeeld. Als $n$ vervolgens niet deelbaar is door 3, dan kan $n$ ook de veelvouden van drie worden gedeeld.

Deze methode kan worden versneld door van tevoren een lijst te maken met priemgetallen, bijvoorbeeld met behulp van de zeef van Eratosthenes en te kijken of het te controleren getal $n$ door een van deze priemgetallen kan worden gedeeld. Als dit het geval is, is het getal samengesteld en is het antwoord bepaald.

Probabilistische tests

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 ten minste 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 2^−k. 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

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 aⁿ⁻¹ 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 ten minste 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

De Miller-Rabin priemgetaltest is niet alleen een probabilistische methode, deze heeft ook een deterministische versie. 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. 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

• Dit artikel of een eerdere versie ervan is een (gedeeltelijke) vertaling van het artikel Primality test op de Engelstalige Wikipedia, dat 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.