Algorytm Schoofa

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Algorytm Schoofa - algorytm służący do obliczania liczby punktów na krzywej eliptycznej nad ciałem skończonym. Metoda ta została opublikowana w roku 1985 przez Rene Schoofa i była pierwszą efektywną (tzn. działającą w czasie wielomianowym) metodą rozwiązującą ten problem.

Działanie algorytmu opiera się na często stosowanej w algorytmach teorioliczbowych obserwacji, że aby obliczyć wartość jakiejś dużej liczby n, wystarczy obliczyć ją modulo kilka "małych" liczb pierwszych. Ostateczny wynik można wtedy uzyskać, stosując konstruktywną wersję chińskiego twierdzenia o resztach.

Czas działania metody Schoofa w jej pierwotnej wersji wynosi O((log q)^8), gdzie q jest wielkością ciała bazowego. Mimo, że jest to czas wielomianowy, w praktyce wersja ta jest zbyt wolna, aby ją stosować w interesujących i ważnych z punktu widzenia praktycznego przypadkach. Udoskonalone wersje algorytmu działają w czasie O((log q)^6). Rozwinięciem algorytmu Schoofa jest algorytm Schoofa-Elkiesa-Atkina ("algorytm SEA"), działający jeszcze szybciej, bo w czasie O((log q)^5).

Algorytm Schoofa jest ważny z punktu widzenia teoretycznego, zaś jego udoskonalenia są nieodzowne w implementacji wielu innych algorytmów w teorii liczb i kryptografii, jak np. test pierwszości ECPP czy generowanie bezpiecznych kryptograficznie krzywych eliptycznych.

Bibliografia[edytuj | edytuj kod]

  • R. Schoof, Elliptic curves over finite fields and the computation of square roots mod p, Mathematics of Computation, Volume 44, 1985