Test pierwszości AKS — część 2

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ą.