Przejdź do zawartości

Test pierwszości ECPP

Z Wikipedii, wolnej encyklopedii

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

[edytuj | edytuj kod]

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 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):

  1. 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).
  2. 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ą.
  3. 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

[edytuj | edytuj kod]

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 algorytmu[2], 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ą LR[3].

Historia

[edytuj | edytuj kod]

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.

Przypisy

[edytuj | edytuj kod]
  1. A.O.L. Atkin, F. Morain Elliptic Curves and Primality Proving, 1992.
  2. F. Morain, Implementing the Asymptotically Fast Version of the Elliptic Curve Primality Proving Algorithm, 21 października 2005.
  3. N. Lygeros, F. Morain, O. Rozier.
  4. S. Goldwasser, J. Killian, Almost All Primes Can Be Quickly Certified, Proc. 18th STOC (Berkeley, 28–30 maja 1986), s. 316–329.
  5. A.O.L. Atkin, Manuskrypt notatek z wykładu na konferencji w Boulder (Kolorado), 1986.