Test pierwszości AKS

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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 czasie wielomianowym.

Znaczenie[edytuj]

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

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

,

która jest prawdziwa wtedy i tylko wtedy, gdy 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 , o ile 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 . 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 i niewielkiego zbioru liczb A, tak żeby tylko liczby pierwsze spełniały ją dla wszystkich ze zbioru A.

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

, gdzie jest największym dzielnikiem pierwszym ,
,
.

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

W drugiej części przeprowadzana jest odpowiednia liczba testów w pierścieniu ilorazowym wielomianów . Każdy test polega na sprawdzeniu równości dwóch wielomianów:

jeśli

dla wszystkich dodatnich , takich że:

,

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

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

Bibliografia[edytuj]

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