Test pierwszości AKS


Test pierwszości AKS w encyklopedii

Z Wikipedii, wolnej encyklopedii Przejdź do nawigacji Przejdź do wyszukiwania

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

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 kod

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

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

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

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

i faktu że:

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

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

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

P ( r 1 ) = q , {\displaystyle P(r-1)=q,} gdzie P ( x ) {\displaystyle P(x)} jest największym dzielnikiem pierwszym x , {\displaystyle x,} q 4 r log 2 n , {\displaystyle q\geqslant 4{\sqrt {r}}\log _{2}n,} n k 1   ( mod r ) . {\displaystyle n^{k}\not \equiv 1\ (\operatorname {mod} \,r).}

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

W drugiej części przeprowadzana jest odpowiednia liczba testów w pierścieniu ilorazowym wielomianów Z n x / ( x r 1 ) . {\displaystyle \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 ( x n a )   ( mod n , x r 1 ) {\displaystyle (x-a)^{n}\equiv (x^{n}-a)\ (\operatorname {mod} \,n,x^{r}-1)}

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

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

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

Ponieważ czas działania obu części zależy od wielkości r , {\displaystyle r,} podanie górnego ograniczenia na r {\displaystyle r} wystarczyło do określenia złożoności algorytmu na O ( log 12 + ϵ n ) {\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 O ( log 6 + ϵ n ) . {\displaystyle \mathrm {O} (\log ^{6+\epsilon }n).}

Bibliografia | edytuj kod

  • Manindra Agrawal, Neeraj Kayal, Nitin Saxena, „PRIMES is in P”, Annals of Mathematics 160 (2004), no. 2, s. 781–793.
Na podstawie artykułu: "Test pierwszości AKS" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy