Schoof's algorithm

Schoof's algorithm allows to calculate the number of points on an elliptic curve over a finite field and is used mostly in elliptic curve cryptography.

Due to the 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}}$. The 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 $q^{8}$ and with several improvements can be reduced to $O(q^{6})$, which is adequate for $q<256$ on a PC. Note that the Schoof-Elkies-Atkin has only $O(q^{5})$ time complexity and thus is always faster.

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 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 implementation for $E(\mathbb {F} _{p})$ with prime $p$.
• Schoof's algorithm implementation for $E(\mathbb {F} _{2^{m}})$.