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.

Współczesna wersja metody ECPP^[1], bazuje na krzywych eliptycznych z mnożeniem zespolonym i teorii form modularnych. Punktem wyjścia jest następujące twierdzenie:

Niech ${\displaystyle N}$ będzie liczbą całkowitą względnie pierwszą z ${\displaystyle 6,}$ ${\displaystyle E}$ krzywą eliptyczną nad ${\displaystyle \mathbb {Z} /N\mathbb {Z} ,}$ ${\displaystyle P}$ punktem na ${\displaystyle E,}$ ${\displaystyle m}$ i ${\displaystyle s}$ dwiema liczbami całkowitymi, dla których ${\displaystyle s|m.}$ Dla każdej liczby pierwszej ${\displaystyle q}$ dzielącej ${\displaystyle s,}$ oznaczmy ${\displaystyle (m/q)P=(x_{q}:y_{q}:z_{q}).}$ Załóżmy, że ${\displaystyle mP=0_{E}}$ (element neutralny ${\displaystyle E}$), oraz że ${\displaystyle z_{q}}$ jest względnie pierwsze z ${\displaystyle N}$ dla wszystkich ${\displaystyle q.}$ Przy powyższych założeniach, jeśli ${\displaystyle p}$ jest dzielnikiem pierwszym ${\displaystyle N,}$ to ${\displaystyle s}$ jest dzielnikiem liczności ${\displaystyle E(\mathbb {Z} /p\mathbb {Z} ).}$ Ponadto, jeśli ${\displaystyle s>({\sqrt{N}}+1)^{2},}$ to ${\displaystyle 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ą ${\displaystyle E}$ nad ${\displaystyle \mathbb {Z} /N\mathbb {Z} ,}$ dla której liczba punktów ${\displaystyle m}$ spełnia warunek ${\displaystyle m=2q,}$ gdzie ${\displaystyle q}$ jest prawdopodobną liczbą pierwszą (można to wydajnie sprawdzić, stosując np. test Millera-Rabina).
2. Jeśli ${\displaystyle E}$ i ${\displaystyle m}$ spełniają założenia powyższego twierdzenia przy ${\displaystyle s=m,}$ to stanowi to dowód, że ${\displaystyle N}$ jest liczbą pierwszą; w przeciwnym wypadku, że jest liczbą złożoną.
3. Aby udowodnić pierwszość liczby ${\displaystyle 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.

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

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

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

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

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

${\displaystyle 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^[3].

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

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