SCHOOF'S ALGORITHM

'Schoof's algorithm', first described by R. Schoof in 1985, allows one to calculate the number of points on an elliptic curve over a finite field and is used mostly in elliptic curve cryptography.
From Hasse's theorem on elliptic curves the number of point on a curve is roughly known:
:$|E(mathbb\{F\}\_q)|\; =\; q\; +\; 1\; pm\; 2\; sqrt\{q\}$,
so to find the exact number it is enough to find it modulo $R\; >\; 4\; sqrt\{q\}$. Schoof's algorithm calculates
:$q+1\; -\; |E(mathbb\{F\}\_q)|\; pmod\{r\_i\}$
for several small primes $r\_i$, where $prod\; r\_i\; =\; R$, and uses the Chinese remainder theorem to combine the results.
The running time of the original algorithm is proportional to $(log\; q)^8$ and with several improvements can be reduced to $O((log\; q)^6)$, which is adequate for on a personal computer.
The algorithm has been extended by Noam Elkies and A. O. L. Atkin to give the Schoof-Elkies-Atkin algorithm, which has only $O((log\; q)^5)$ time complexity and thus is asymptotically faster.

Contents

References

Implementations

References

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

Implementations

Several algorithms were implemented in C++ by Mike Scott and are available with [ftp://ftp.compapp.dcu.ie/pub/crypto/ source code]. The implementations are free (no terms, no conditions), but they use MIRACL library which is only free for non-commercial use. Note that (unmodified) programs may be used to generate curves for commercial use. There are

★ Schoof's algorithm [ftp://ftp.compapp.dcu.ie/pub/crypto/schoof.cpp implementation] for $E(mathbb\{F\}\_p)$ with prime $p$.

★ Schoof's algorithm [ftp://ftp.compapp.dcu.ie/pub/crypto/schoof2.cpp implementation] for $E(mathbb\{F\}\_\{2^m\})$.