Test pierwszości ECPP (ang. elliptic curve primality proving) – rodzina algorytmów służących do dowodzenia, że dana liczba naturalna jest liczbą pierwszą, wykorzystujących teorię krzywych eliptycznych. Zamiennie stosuje się określenie algorytm Atkina-Goldwasser-Kiliana-Morain’a, od nazwisk matematyków, którzy zasadniczo przyczynili się do rozwinięcia tej metody. ECPP jest w praktyce jednym z najbardziej wydajnych algorytmów testowania pierwszości dużych liczb, o oczekiwanym czasie działania wielomianowo zależnym od długości zapisu liczby, aczkolwiek nie zostało to dotychczas udowodnione dla wszystkich możliwych przypadków.
Zarys algorytmu Współczesna wersja metody ECPPA.O.L. Atkin, F. Morain Elliptic Curves and Primality Proving, 1992., bazuje na krzywych eliptycznych z mnożeniem zespolonym i teorii form modularnych. Punktem wyjścia jest następujące twierdzenie:
Niech będzie liczbą całkowitą względnie pierwszą z krzywą eliptyczną nad punktem na i dwiema liczbami całkowitymi, dla których Dla każdej liczby pierwszej dzielącej oznaczmy Załóżmy, że (element neutralny ), oraz że jest względnie pierwsze z dla wszystkich Przy powyższych założeniach, jeśli jest dzielnikiem pierwszym to jest dzielnikiem liczności Ponadto, jeśli to jest liczbą pierwszą.
Połączenie tego twierdzenia z metodą zliczania liczby punktów na krzywej eliptycznej działającą w czasie wielomianowym (jak np. algorytm Schoofa) daje następującą szybką metodę dowodzenia pierwszości (procedura Goldwasser-Killiana): Wybierz losowo krzywą eliptyczną nad dla której liczba punktów spełnia warunek gdzie jest prawdopodobną liczbą pierwszą (można to wydajnie sprawdzić, stosując np. test Millera-Rabina). Jeśli i spełniają założenia powyższego twierdzenia przy to stanowi to dowód, że jest liczbą pierwszą; w przeciwnym wypadku, że jest liczbą złożoną. Aby udowodnić pierwszość liczby wywołaj rekurencyjnie tę samą procedurę.
Tradycyjna procedura Goldwasser-Killiana przedstawiona powyżej ma tę wadę, że odwołuje się do algorytmu zliczania punktów na dowolnej krzywej eliptycznej. Algorytmy takie (np. algorytm Schoofa) są bardzo skomplikowane, i, mimo że działają w czasie wielomianowym, to w praktyce są bardzo wolne. Atkin i Morain zaproponowali modyfikację algorytmu z zastosowaniem krzywych eliptycznych z mnożeniem zespolonym, która stanowi podstawę współczesnej wersji algorytmu ECPP. Jest ona dość skomplikowana i pełna szczegółów technicznych; prezentacja jej wykracza poza ramy niniejszego artykułu. W zarysie procedura Atkina-Moraina polega na konstrukcji (w przeciwieństwie do losowego wybierania) krzywych eliptycznych spełniających założenia powyższego twierdzenia, tzn. o odpowiedniej liczbie punktów. Konstrukcja odbywa się dzięki wykorzystaniu związków między własnościami kwadratowych ciał liczbowych, funkcji modularnych (Dedekinda i Webera) i krzywych eliptycznych, które zaczerpnięte są z teorii ciała klas.
Wydajność algorytmu Od strony teoretycznej złożoność metody ECPP jest trudna do analizowania, ponieważ algorytm wykorzystuje jednocześnie wiele metod z różnych nowoczesnych dziedzin matematyki. Dla oryginalnej, historycznej metody Goldwasser-Killiana z wykorzystaniem algorytmu Schoofa, przy założeniu pewnej powszechnie uważanej za prawdziwą (ale dotychczas nieudowodnionej) hipotezy teorioliczbowej dotyczącej rozkładu liczb pierwszych w małych przedziałach, można pokazać, że oczekiwany czas działania wynosi
Dla podstawowej wersji algorytmu Atkina-Moraina uważa się, że oczekiwany czas działania wynosi
dla dowolnie małej stałej Hipoteza ta wyprowadzona jest jednak na podstawie bardzo wielu nieudowodnionych twierdzeń czy wręcz heurystyk. Najnowsze wersje algorytmuF. Morain, Implementing the Asymptotically Fast Version of the Elliptic Curve Primality Proving Algorithm, 21 października 2005., będące udoskonaloną wersją wariantu Atkina-Moraina (tzw. wariant Lenstry-Lenstry-Shallita), działają hipotetycznie jeszcze szybciej, nawet w czasie
W praktyce algorytm ECPP jest jedną z najszybszych metod testowania pierwszości dużych liczb o dowolnej postaci. Jest na tyle szybki, że umożliwia na typowych komputerach biurowych dowodzenie pierwszości liczb o kilku tysiącach cyfr dziesiętnych w czasie rzędu godzin. Rekordem (listopad 2011) jest dowód pierwszości liczby 26643-cyfrowej, będącej liczbą pierwszą LRN. Lygeros, F. Morain, O. Rozier..
Historia Pierwotnymi twórcami metody ECPP byli Shafrira Goldwasser i Joe Killian, którzy przedstawiliS. Goldwasser, J. Killian, Almost All Primes Can Be Quickly Certified, Proc. 18th STOC (Berkeley, 28–30 maja 1986), s. 316–329. ją w roku 1986. Niemal w tym samym czasie metodę tę opisał A.O.L. AtkinA.O.L. Atkin, Manuskrypt notatek z wykładu na konferencji w Boulder (Kolorado), 1986..
Na przestrzeni lat algorytm ECPP był stopniowo udoskonalany przez wielu ludzi, m.in. François Morain’a.
Przypisy
ECPP