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)|\; leq\; 2sqrt\{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.

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 [http://indigo.ie/~mscott/ 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\})$.

References

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