Test pierwszości AKS

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.

Znaczenie

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).

Podstawa testu

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

$(x-a)^{n}\equiv (x^{n}-a)\ (\operatorname {mod} \,n),$

jest prawdziwa wtedy i tylko wtedy, gdy $n$ jest liczbą pierwszą. $x$ 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:

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

i faktu że:

${n \choose k}\equiv 0\ (\operatorname {mod} \,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\geqslant 4{\sqrt {r}}\log _{2}n,$

$n^{k}\not \equiv 1\ (\operatorname {mod} \,r).$

W tej części niezbędne jest sprawdzenie, że $n$ nie dzieli się przez żadne $p\leqslant 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)\ (\operatorname {mod} \,n,x^{r}-1)$

dla wszystkich dodatnich $a,$ takich że:

$a\leqslant 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 $\mathrm {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 $\mathrm {O} (\log ^{6+\epsilon }n).$

Bibliografia

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