Teoria

Zagadnienia matematyczne związane z wyprowadzeniem algorytmu, na którym opiera się AKS, są dosyć proste.

Wiadomo bowiem, że dla n liczb pierwszych zachodzi następujące równanie:

a dla jednego, wyszczególnionego wielomianu w(x)=x-a uogólnienie równa się:

Jest to uogólnione Małe Twierdzenie Fermata. Zachodzi ono tylko dla liczb pierwszych, kiedy nP. Jest to w pewnym sensie test pierwszości, jednak jeszcze nie taki jak jest potrzebny. To równanie ma złożoność wykładniczą i nie nadaje się do dużych liczb, jednak po zastosowaniu specjalnego wielomianu x^r-1, przez który są dzielone modulo obie strony równania złożoność całego testu bardzo maleje.

AKS ma dwie części dążące do sprawdzenia, czy liczba n jest potęgą liczby pierwszej. Pierwsza to znalezienie parametrów równania r i s. W drugiej fazie algorytmu sprawdzane są wartości b względem s.

Istnieją dwa twierdzenia AKS i AKS z rozwinięciem Lanstra. Pierwsze z nich jest nieco gorsze i w dalszej części tworzenia algorytmu AKS trzeba korzystać z twierdzenia Fouvryego, przez co stosowane jest twierdzenie drugie. Należy założyć, że n∈C⁺ i tak jak r jest liczbą pierwszą, a v rzędem n modulo r. Dalej zbiór S jest zbiorem s liczb a i a’ całkowitych, takich że ich NWD wynosi 1, a dla każdego d, które jest dzielnikiem φ(r)/ν zachodzi nierówność:

oraz dla wszystkich aS w pierścieniu Z_n[x]/x^r-1 zachodzi równanie (x+a)ⁿ≡(xⁿ+a). Przy takich założeniach wynika, że n jest potęgą liczby pierwszej. Jeśli zrobić kolejne założenie, że n jest pierwiastkiem pierwotnym modulo r, to ν=φ(r), a całe twierdzenie się upraszcza.

Główny wzór (równanie), czyli odpowiednio przekształcone Małe Twierdzenie Fermata, działa oczywiście tylko dla liczb pierwszych. Mając obliczone r, w kolejnych krokach algorytmu podstawia się pod zmienna a kolejne liczby naturalne z przedziału od 1 do wartości pierścienia Jeśli dla wszystkich a równanie pozostaje spełnione, to wiadomo, że n jest liczbą pierwszą.

Opis algorytmu

Jest wiele rozwinięć algorytmów AKS. Wszystkie oczywiście opierają się na podstawowym, jednak są modyfikacje przyśpieszające działanie. Zmiany i ulepszenia do AKS wprowadzali rożni naukowcy, profesorowie, jednak najlepsze i najważniejsze zmiany wprowadzili Lenstra i Bernstein. Właśnie metoda Lenstry odniosła największy sukces. Warto więc skupić się na opisie algorytmu testu liczb pierwszych z zastosowaniem zmian, udogodnień wprowadzonych przez Hendrika Lenstra.

Ogólnie można przyjąć, że implementację tego algorytmu można zapisać jako pięciokrokowy plan, w którym poszczególne kroki to dążenie do pewności pierwszości podanej liczby. Na początku trzeba sprawdzić czy liczba, która ma zostać przetestowana jest większa od 1. Jest to zupełnie normalne, gdyż liczba 1, nie jest liczbą pierwszą i nie potrzebne są dalsze obliczenia. Należy więc brać do testowania liczby większe od jeden. Symbolicznie liczbę testowaną można przyjąć jako n. Za n więc będą podstawiane dowolne liczby, które algorytm ma sprawdzić i ustalić ich pierwszość.

Krok pierwszy to sprawdzenie czy:

. Jeżeli tak to nasza liczba n nie jest liczba pierwszą. Jest to bardzo prosty i szybki test, dlatego warto go wykonać na początku sprawdzania liczby. Nie jest on jednak deterministyczny. Istnieją bowiem liczby, których żadna potęga nie daje podanej liczby n, a podana liczba okazuje się liczbą złożoną. Na przykład gdy n=3 wtedy test wykazuje wynik negatywny, czyli brak równości - liczba jest pierwsza. Jest to przypadek w którym liczba była faktycznie pierwsza, ale gdyby za n podstawić liczbę 10? Test nadal wykaże jej pierwszość, ponieważ żadna liczba do potęgi nie daje dziesiątki. Jest więc to niewystarczające sprawdzenie. Potrzebne są inne testy.

Krok drugi, czyli znajdowanie liczby r, liczby potrzebnej w głównym teście AKS. W kroku tym nie zachodzi sprawdzanie liczby n, a jedynie wyznaczanie liczby potrzebnej do późniejszych obliczeń. Najmniejszą liczbę r szuka się ze wzoru:

We wzorze tym o_r(n) definiowane jest w następujący sposób. Z dwóch zbiorów liczb naturalnych N i Z należy wziąć kolejne liczby r i n (liczba wybrana uprzednio do testu jej pierwszości), tak, by ich względna pierwszość wynosiła 1, czyli (n,r)=1. Szukać należy najmniejszej liczby spełniającej ten warunek. Posłużyć się należy wzorem: n^k=1(mod r), a dla najmniejszego k jest to właśnie o_r(n). Nierówność wykonywana jest tak długo aż pojawi się r, które ją spełnia. Wartość jej musi zostać zapisana i możliwe jest przejście do następnego kroku.

Krok trzeci to wyliczanie podwójnej nierówności:

czyli sprawdzenie, czy kolejne liczby naturalne a, spełniają warunek względnej pierwszości z n. Jeżeli tak to spełnione są oba warunki nierówności. Należy jeszcze sprawdzić czy a, które z wyliczeń spełnia podstawowy warunek kroku jest mniejsze, lub równe wyliczonej w poprzednim kroku liczbie r. Taka sytuacja oznacza, że podana liczba testowana, nie jest liczba pierwszą, ponieważ istnieje inna liczba, mniejsza od r, która spełnia warunek pierwszości, ale nie spełnia warunków z kroku drugiego. Jeżeli jednak nie istnieje taka liczba a, wtedy należy przejść do następnego kroku, gdyż i w tym można napotkać na liczby spełniające warunek tego kroku, a nie będące liczbami pierwszymi.

Krok czwarty to bardzo łatwy test. Polega jedynie na sprawdzeniu, czy liczba n jest mniejsza, bądź równa r. Jeżeli warunek jest spełniony, podana liczba testowa, jest liczbą pierwszą i nie trzeba przechodzić do ostatniego testu AKS.

Krok piąty - AKS! Dla liczby a z przedziału od 1 do pierścienia sprawdzana jest nierówność. φ(r) to funkcja Eulera określająca ilość liczb względnie pierwszych z liczbą r. Równanie AKS sprawdzania pierwszości liczby n wygląda następująco:

X to oznaczenie wielomianu, a nie liczby, wiec nawias podnoszony do potęgi n to wielomian X+a podnoszony do tej potęgi. Obie strony równania są dzielone modulo najpierw przez n, a następnie przez specjalny wielomian X^r-1. Jeżeli po przejściu całego zakresu liczy a, każde z równań będzie spełnione, oznacza to, że testowana liczba jest liczbą deterministycznie pierwszą! Test zostaje zakończony.

Są liczby, zwane liczbami Carmichaela, które nie spełniają założenia i przechodzą przez test AKS. Są to np. liczby:

561	=	3 · 11 · 17	Najmniejsza z tych liczb
1105	=	5 · 13 · 17	(4 | 1104, 12 | 1104, 16 | 1104)
1729	=	7 · 13 · 19	(6 | 1728, 12 | 1728, 18 | 1728)
2465	=	5 · 17 · 29	(4 | 2464, 16 | 2464, 28 | 2464)
2821	=	7 · 13 · 31	(6 | 2820, 12 | 2820, 30 | 2820)
6601	=	7 · 23 · 41	(6 | 6600, 22 | 6600, 40 | 6600)
8911	=	7 · 19 · 67	(6 | 8910, 18 | 8910, 66 | 8910)

Przechodzą one sam test AKS, jednak nie przechodzą pozostałych, wiec cały test jest deterministyczny dla wszystkich liczb naturalnych.