Algorytm Schoofa

Algorytm Schoofa - algorytm służący do obliczania ilości 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

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