Schoof's algorithm

Encyclopedia : S : SC : SCH : 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_q)| = q + 1 \pm 2 \sqrt],

so to find the exact number it is enough to find it modulo [R > 4 \sqrt]. Schoof's algorithm calculates

[q+1 - |E(\mathbb_q)| \pmod]

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 < 256] 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.

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_p)] with prime [p].
Schoof's algorithm [implementation] for [E(\mathbb_)].

From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.