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 ${\displaystyle n}$≥2 jest liczbą całkowitą, ${\displaystyle a}$ jest również liczbą całkowitą względnie pierwszą z ${\displaystyle n,}$ test AKS opiera się na twierdzeniu, że równość:

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

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

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

i faktu że:

${\displaystyle {n \choose k}\equiv 0\ (\operatorname {mod} \,n)}$

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

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

${\displaystyle P(r-1)=q,}$ gdzie ${\displaystyle P(x)}$ jest największym dzielnikiem pierwszym ${\displaystyle x,}$

${\displaystyle q\geqslant 4{\sqrt {r}}\log _{2}n,}$

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

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

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

jeśli

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

dla wszystkich dodatnich ${\displaystyle a,}$ takich że:

${\displaystyle a\leqslant 2{\sqrt {r}}\log _{2}n,}$

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

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