Test pierwszości AKS

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

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

Znaczenie

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

Podstawa testu

Test AKS opiera się na równości:

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

która jest prawdziwa wtedy i tylko wtedy gdy n jest liczbą pierwszą. Równość ta jest uogólnieniem małego twierdzenia Fermata na wielomiany i można ją łatwo udowodnić korzystając z rozwinięcia

$(x-a)^n=\sum_{k=0}^n{n \choose k}x^k(-a)^{n-k}$

i faktu że

${n \choose k} \equiv 0 \pmod{n}$

dla wszystkich 0 < k < n, o ile n 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 $x^{r}-1$. 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 r i niewielkiego zbioru liczb A, tak żeby tylko liczby pierwsze spełniały ją dla wszystkich a ze zbioru A.

Algorytm składa się z dwóch części. Pierwsza polega na znalezieniu odpowiedniej liczby pierwszej $r = kq + 1$, takiej że:

• $P(r - 1) = q$, gdzie $P(x)$ jest największym dzielnikiem pierwszym $x$,
• $q \ge 4 \sqrt{r} \log_{2}(n),$
• $n^k \not\equiv 1 \pmod{r}.$

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

W drugiej części przeprowadzana jest odpowiednia liczba testów w pierścieniu ilorazowym wielomianów $\mathbb Z_n[x]/(x^r-1)$. Każdy test polega na sprawdzeniu równości dwóch wielomianów: jeśli

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

dla wszystkich dodatnich a takich że

$a \le 2 \sqrt{r} \log_{2}(n),$

to n 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 r zawsze można znaleźć, ustalenie wielkości tego r i udowodnienie że testy przeprowadzone w drugiej części są wystarczające do stwierdzenia pierwszości n.

Ponieważ czas działania obu części zależy od wielkości r, podanie górnego ograniczenia na r wystarczyło do określenia złożoności algorytmu na O$(\log^{12+\epsilon}(n))$. 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 O$(\log^{6+\epsilon}(n))$.

Bibliografia

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