Schoof's algorithm

From Wikipedia, the free encyclopedia

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 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 $q < 2 56$ 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.

[edit] 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