Test pierwszości AKS

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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