AKS-test

De AKS-test is een priemgetaltest; een methode om te controleren of een getal een samengesteld getal of een priemgetal is. De AKS-test is vernoemd naar zijn bedenkers: Manindra Agrawal, Neeraj Kayal en Nitin Saxena. Zij publiceerden het algoritme in hun artikel Primes is in P.^[1]

Al snel werd hun resultaat door anderen verbeterd. In 2005 beschreven Carl Pomerance en H. W. Lenstra, Jr. een variant van de AKS-test, die O(log^6+ε n) operaties nodig heeft om een getal n te testen. Dit was duidelijk een verbetering ten opzichte van de grens van O(log^12+ε n) in het originele algoritme.^[2]

Het belangrijkste van de AKS-test is dat de test vier eigenschappen (algemeen, polynomiaal, deterministisch en zonder aannamen) bundelt, die niet eerder gebundeld waren:

• Algemeen: De test werkt voor alle priemgetallen. Andere snelle tests als de Lucas–Lehmertest (werkt alleen voor mersennepriemgetallen) of de Pépintest (alleen voor fermatgetallen) zijn niet voor alle priemgetallen geschikt.
• Polynomiaal: Zoals we hierboven zagen, werkt de test in polynomiale tijd. Er waren wel eerder sluitende priemgetaltests bekend die in exponentiële tijd werkten, maar nog niet eerder in polynomiale tijd.
• Deterministisch: De test bepaalt deterministisch of een getal priem is of niet. Tests als de Miller-Rabin-priemgetaltest kunnen ook in polynomiale tijd testen of een getal al dan niet priem is, maar leveren een antwoord met slechts een bepaalde mate van zekerheid (er is 99,... % kans dat n een priemgetal is).
• Zonder aannamen: De test is niet gebaseerd op nog onbewezen vermoedens. De deterministische versie van de Miller-Rabin-priemgetaltest is gebaseerd op de nog niet bewezen Algemene Riemann-hypothese.

De test is gebaseerd op het volgende principe:

${\displaystyle (x-a)^{n}\equiv (x^{n}-a){\pmod {n}}\qquad (1)}$

Dit is een afleiding van de kleine stelling van Fermat voor polynomen en kan afgeleid worden uit de kleine stelling van Fermat in combinatie met het binomium van Newton en de volgende eigenschap van de binomiaalcoëfficiënt:

${\displaystyle {n \choose k}\equiv 0{\pmod {n}}}$ voor alle k, 0 < k < n dan en slechts dan als n een priemgetal is.

Hoewel dit zelf al een priemgetaltest is, werkt hij in exponentiële tijd. Daarom maakt men voor de AKS-test gebruik van de equivalentie:

${\displaystyle (x-a)^{n}\equiv (x^{n}-a){\pmod {n,x^{r}-1}}\qquad (2)}$

wat hetzelfde is als:

${\displaystyle (x-a)^{n}-(x^{n}-a)=nf+(x^{r}-1)g\qquad (3)}$

voor zekere polynomen f en g. Dit kan getest worden in een polynominale tijd. Merk op dat alle priemgetallen aan deze gelijkheid voldoen (wanneer we r = 0 kiezen in (3), krijgen we (1), die geldt voor alle priemgetallen). Er zijn echter ook enkele samengestelde getallen die hier aan voldoen. Het principe van de AKS-test berust er nu op, dat er een r bestaat die klein genoeg is met een bijbehorende verzameling getallen A, zodanig dat als geldt dat de vergelijking klopt voor die kleinere verzameling getallen, dat het getal n dan een priemgetal is.

Het originele^[1] algoritme werkt als volgt:

Invoer: een geheel getal n > 1.

1. Als n = a^b, met gehele getallen a > 0 en b > 1, uitvoer samengesteld.
2. Vind het kleinste getal r zodat o_r(n) > log²(n).
3. Als 1 < ggd(a,n) < n voor een zekere a ≤ r, uitvoer samengesteld.
4. Als n ≤ r, uitvoer priem.
5. Voor a = 1 tot ${\displaystyle \scriptstyle \lfloor \scriptstyle {\sqrt {\varphi (r)}}\log(n)\scriptstyle \rfloor }$, dan

   als (X+a)ⁿ≠ Xⁿ+a (mod X^r − 1,n), uitvoer samengesteld.

6. Uitvoer priem.

Hierin is o_r(n) is het kleinste getal k zodat n^k ≡ 1 (mod r) (oftewel de multiplicatieve orde van n modulo r). Bovendien bedoelen we met log de logaritme met grondtal 2 en ${\displaystyle \scriptstyle \varphi (r)}$ is de Euler-phi functie van r.

Wanneer n een priemgetal is, zal de uitvoer van het algoritme altijd priem zijn: aangezien n een priemgetal is, zullen stap 1. en 3. nooit samengesteld als uitvoer geven. Stap 5. zal ook nooit samengesteld als uitvoer geven, omdat (2) waar is voor alle priemgetallen n. Daarom zal de uitvoer van het algoritme priem zijn, ofwel in stap 4. ofwel in stap 6.

Omgekeerd, als n samengesteld is, zal de uitvoer van het algoritme altijd samengesteld zijn: stel dat de uitvoer priem is, dan zal dit gebeuren in stap 4. of stap 6. In het eerste geval, aangezien n ≤ r, heeft n een factor a ≤ r zodanig dat 1 < gcd(a,n) < n, waardoor de uitvoer in stap 3. samengesteld zou zijn geweest. De overgebleven mogelijkheid is dat de uitvoer in stap 6. priem is. In het originele artikel^[1] is bewezen dat dit niet zal gebeuren, omdat de gelijkheden die worden getest in stap 5. voldoende zijn om te garanderen dat de uitvoer samengesteld is.

Om te bewijzen dat het algoritme correct is, moeten we twee dingen bewijzen. Ten eerste dat de r uit stap 2. altijd gevonden kan worden^[1] en ten tweede de beweringen die hierboven beschreven staan. Bovendien wordt in het artikel^[1] bewezen dat het algoritme werkt in polynomiale tijd.

• (en) Achtergrondartikel