Test pierwszości ECPP

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 ECPP, bazuje na krzywych eliptycznych z mnożeniem zespolonym i teorii form modularnych. Punktem wyjścia jest następujące twierdzenie:

Niech $N$ będzie liczbą całkowitą względnie pierwszą z $6,$ $E$ krzywą eliptyczną nad $\mathbb {Z} /N\mathbb {Z} ,$ $P$ punktem na $E,$ $m$ i $s$ dwiema liczbami całkowitymi, dla których $s|m.$ Dla każdej liczby pierwszej $q$ dzielącej $s,$ oznaczmy $(m/q)P=(x_{q}:y_{q}:z_{q}).$ Załóżmy, że $mP=0_{E}$ (element neutralny $E$), oraz że $z_{q}$ jest względnie pierwsze z $N$ dla wszystkich $q.$ Przy powyższych założeniach, jeśli $p$ jest dzielnikiem pierwszym $N,$ to $s$ jest dzielnikiem liczności $E(\mathbb {Z} /p\mathbb {Z} ).$ Ponadto, jeśli $s>({\sqrt[{4}]{N}}+1)^{2},$ to $N$ 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):

1. Wybierz losowo krzywą eliptyczną $E$ nad $\mathbb {Z} /N\mathbb {Z} ,$ dla której liczba punktów $m$ spełnia warunek $m=2q,$ gdzie $q$ jest prawdopodobną liczbą pierwszą (można to wydajnie sprawdzić, stosując np. test Millera-Rabina).
2. Jeśli $E$ i $m$ spełniają założenia powyższego twierdzenia przy $s=m,$ to stanowi to dowód, że $N$ jest liczbą pierwszą; w przeciwnym wypadku, że jest liczbą złożoną.
3. Aby udowodnić pierwszość liczby $q,$ 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

$O((\log N)^{10}).$

Dla podstawowej wersji algorytmu Atkina-Moraina uważa się, że oczekiwany czas działania wynosi

$O((\log N)^{6+\epsilon })$

dla dowolnie małej stałej $\epsilon .$ Hipoteza ta wyprowadzona jest jednak na podstawie bardzo wielu nieudowodnionych twierdzeń czy wręcz heurystyk. Najnowsze wersje algorytmu, będące udoskonaloną wersją wariantu Atkina-Moraina (tzw. wariant Lenstry-Lenstry-Shallita), działają hipotetycznie jeszcze szybciej, nawet w czasie

$O((\log N)^{4+\epsilon }).$

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

Historia

Pierwotnymi twórcami metody ECPP byli Shafrira Goldwasser i Joe Killian, którzy przedstawili ją w roku 1986. Niemal w tym samym czasie metodę tę opisał A.O.L. Atkin.

Na przestrzeni lat algorytm ECPP był stopniowo udoskonalany przez wielu ludzi, m.in. François Morain’a.