Z Wikipedii

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.^[1]. 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.

[edytuj] 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).

[edytuj] Podstawa testu

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

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

i faktu że

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,
• 
• 

W tej części niezbędne jest sprawdzenie, że n nie dzieli się przez żadne . 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 ciele skonczonym GF(n^r). Każdy test polega na sprawdzeniu równości dwóch wielomianów w tym ciele: jeśli

dla wszystkich dodatnich a takich że

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 + ε}(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 + ε}(n)).

[edytuj] Źródło

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

[edytuj] Linki zewnętrzne

• Dawid Chojak, Dariusz Maćkowiak i Michał Stadnicki: Wielomianowy i deterministyczny algorytm testowania pierwszości liczb AKS (Agrawala-Kayala-Saxeny).
• Maciej Wiśniewski, Paweł Walkiewicz i Jakub Ratajczak: Badanie i implementacja Testu AKS.