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 ${\displaystyle 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 ${\displaystyle O((\log q)^{8}),}$ gdzie ${\displaystyle 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 ${\displaystyle O((\log q)^{6}).}$ Rozwinięciem algorytmu Schoofa jest algorytm Schoofa-Elkiesa-Atkina („algorytm SEA”), działający jeszcze szybciej, bo w czasie ${\displaystyle 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.

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