The algorithm has applications in elliptic curve cryptography where it is important to know the number of points to judge the difficulty of solving the discrete logarithm problem in the group of points on an elliptic curve.
The algorithm was published by René Schoof in 1985 and it was a theoretical breakthrough, as it was the first deterministic polynomial time algorithm for counting points on elliptic curves.
Before Schoof's algorithm, approaches to counting points on elliptic curves such as the naive and baby-step giant-step algorithms were, for the most part, tedious and had an exponential running time.
This article explains Schoof's approach, laying emphasis on the mathematical ideas underlying the structure of the algorithm.
be an elliptic curve defined over the finite field
satisfying the curve equation and a point at infinity
In order to count points on an elliptic curve, we compute the cardinality of
satisfies This powerful result, given by Hasse in 1934, simplifies our problem by narrowing down
to a finite (albeit large) set of possibilities.
is no loss since we can always pick a bigger prime to take its place to ensure the product is big enough.
The Frobenius endomorphism satisfies a quadratic polynomial which is linked to the cardinality of
Schoof's idea was to carry out this computation restricted to points of order
The lth division polynomial is such that its roots are precisely the x coordinates of points of order l. Thus, to restrict the computation of
to the l-torsion points means computing these expressions as functions in the coordinate ring of E and modulo the lth division polynomial.
we obtain: Note that this computation fails in case the assumption of inequality was wrong.
satisfies for all l-torsion points P. As mentioned earlier, using Y and
If you recall, our initial considerations omit the case of
By definition of addition in the group, any element of order 2 must be of the form
In total, the number of bit operations for each prime
primes, the total complexity of Schoof's algorithm turns out to be
Using fast polynomial and integer arithmetic reduces this to
In the 1990s, Noam Elkies, followed by A. O. L. Atkin, devised improvements to Schoof's basic algorithm by restricting the set of primes
is called an Elkies prime if the characteristic equation:
Atkin showed how to combine information obtained from the Atkin primes with the information obtained from Elkies primes to produce an efficient algorithm, which came to be known as the Schoof–Elkies–Atkin algorithm.
The first problem to address is to determine whether a given prime is Elkies or Atkin.
In order to do so, we make use of modular polynomials, which come from the study of modular forms and an interpretation of elliptic curves over the complex numbers as lattices.
Under the heuristic assumption that approximately half of the primes up to an
bound are Elkies primes, this yields an algorithm that is more efficient than Schoof's, with an expected running time of
Several algorithms were implemented in C++ by Mike Scott and are available with source code.
The implementations are free (no terms, no conditions), and make use of the MIRACL library which is distributed under the AGPLv3.