Test pierwszości AKS (lub test pierwszości Agrawal-Kayal-Saxena) – deterministyczny test pierwszości opublikowany przez Manindra Agrawal, Neeraj Kayal i Nitin Saxena z IIT Kanpur 6 sierpnia 2002 r. w artykule zatytułowanym PRIMES is in P. Za jego opracowanie autorzy zostali uhonorowani Nagrodą Gödla w 2006 r.

Algorytm ten stwierdza czy dana liczba jest pierwsza, czy złożona w czasie wielomianowym.

AKS jest pierwszym opublikowanym algorytmem badającym czy dana liczba jest pierwsza, który jest wielomianowy (szybki), deterministyczny (jednoznaczny) i bezwarunkowy. Oznacza to, że maksymalny czas działania tego algorytmu można opisać funkcją wielomianową z liczby cyfr badanej liczby, pozwalającą udowodnić, że zawsze zwróci on poprawną odpowiedź (a nie tylko z pewnym prawdopodobieństwem), a jego działanie nie opiera się na żadnych nieudowodnionych hipotezach (takich jak np. hipoteza Riemanna).

Przy założeniu, że ≥2 jest liczbą całkowitą, jest również liczbą całkowitą względnie pierwszą z test AKS opiera się na twierdzeniu, że równość:

jest prawdziwa wtedy i tylko wtedy, gdy jest liczbą pierwszą. należy rozumieć jako formalny symbol (przestrzeń wielomianów). Równość ta jest uogólnieniem małego twierdzenia Fermata na wielomiany i można ją łatwo udowodnić korzystając z rozwinięcia:

i faktu że:

dla wszystkich o ile jest liczbą pierwszą. Sama ta równość jest więc już testem pierwszości, ale jej sprawdzenie wymaga wykładniczego czasu. W teście AKS zamiast rozważać pełną wersję tej równości, sprawdza się ją modulo pewien wielomian Oczywiście, równość dalej jest spełniana przez liczby pierwsze, ale mogą istnieć liczby złożone, które zaczynają ją spełniać. Kluczem jest więc znalezienie odpowiedniego i niewielkiego zbioru liczb A, tak żeby tylko liczby pierwsze spełniały ją dla wszystkich ze zbioru A.

Algorytm składa się z dwóch części. Pierwsza polega na znalezieniu odpowiedniej liczby pierwszej takiej że:

gdzie jest największym dzielnikiem pierwszym

W tej części niezbędne jest sprawdzenie, że nie dzieli się przez żadne Jeśli się dzieli, algorytm kończy działanie pokazując, że jest liczbą złożoną.

W drugiej części przeprowadzana jest odpowiednia liczba testów w pierścieniu ilorazowym wielomianów Każdy test polega na sprawdzeniu równości dwóch wielomianów:

jeśli

dla wszystkich dodatnich takich że:

to jest liczbą pierwszą. W każdym innym przypadku jest liczbą złożoną.

Opis algorytmu wymagał uzupełniania o dwa elementy: dowód poprawności oraz ustalenie jego złożoności obliczeniowej. Zostało to zrealizowane przez pokazanie, że odpowiednie zawsze można znaleźć, ustalenie wielkości tego i udowodnienie, że testy przeprowadzone w drugiej części są wystarczające do stwierdzenia pierwszości

Ponieważ czas działania obu części zależy od wielkości podanie górnego ograniczenia na wystarczyło do określenia złożoności algorytmu na . To górne ograniczenie jest bardzo zgrubne – jeśli prawdziwe jest założenie o rozkładzie liczb pierwszych Sophie Germain, to złożoność algorytmu automatycznie maleje do

• Manindra Agrawal, Neeraj Kayal, Nitin Saxena, „PRIMES is in P”, Annals of Mathematics 160 (2004), no. 2, s. 781–793.