Algorytm Schoofa

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

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