AKSprimaliteettitesti

AKSprimaliteettitesti on deterministinen polynomiaikainen algoritmi, jolla voidaan päätellä, onko kokonaisluku n alkuluku. Sen kehittivät Manindra Agrawal, Neeraj Kayal ja Nitin Saxena IIT Kanpurissa, ja se julkaistiin vuonna 2002. Testin merkitys on teoreettinen: se oli ensimmäinen todistettu deterministinen primaliteettiprosessi, joka toimii polynomiaikaisesti ilman sääntämää satunnaisuutta.

Perusidea ja rakenne. AKSprimaliteettitesti perustuu polynomien kongruensseihin mod n ja mod X^r − 1. Kun n on alkuluku, tiettyjen kongruenssien pätevyys seuraa suoraan binomiaalisen lauseen avulla: (X + a)^n ≡ X^n + a (mod n, X^r − 1) pätee tietyllä seleccionoidulla alueella a:lle. Vastakohdasta (jos n on epäprimo) löytyy usein kongruenssien epäyhtenäisyyksiä. Algoritmi etenee käytännössä kolmessa vaiheessa: (1) varmistetaan, ettei n ole täydellinen potenssi; (2) etsitään pienin r, jonka avulla kongruenssien tarkastelu voidaan tehdä tehokkaasti; (3) tarkastetaan kongruenssit kaikille valituille a:lle mod n ja mod X^r − 1. Jos kaikki tarkastukset pitävät paikkansa, n hyväksytään alkulukuna; muuten se todetaan epprimoiseksi.

Vaikutus ja merkitys. AKSprimaliteettitesti osoitti, että primiteetti on päätettävissä deterministisesti polynomiaikaisesti. Tämä oli ratkaiseva teoreettinen virstanpylväs primaliteetin tutkimuksessa. Käytännössä algoritmin johtamat monimutkaisuudet ovat suuremmat kuin useimmat käytännön testit, ja nykyään yleisimpiä ovat probabilistiset menetelmät (esim. Miller–Rabin). AKS tarjoaa kuitenkin kiinteän, ei-satunnaisen pohjan primaliteetin teoriatieteelle.