Schoof's Algorithm is an efficient algorithm to count points on elliptic curves over finite fields. 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 babystep giantstep 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.
Contents 
Let E be an elliptic curve defined over the finite field , where q = p^{n} for p a prime and n an integer . Over a field of characteristic an elliptic curve can be given by a (short) Weierstrass equation y^{2} = x^{3} + Ax + B with . The set of points defined over consists of the solutions satisfying the curve equation and a point at infinity O. Using the group law on elliptic curves restricted to this set one can see that this set forms an abelian group, with O acting as the zero element. In order to count points on an elliptic curve, we compute the cardinality of . Schoof's approach to computing the cardinality makes use of Hasse's theorem on elliptic curves along with the Chinese remainder theorem and division polynomials.
Hasse's theorem states that if is an elliptic curve over the finite field , then satisfies
This powerful result, given by Hasse in 1934, simplifies our problem by narrowing down to a finite (albeit large) set of possibilities. Defining t to be , and making use of this result, we now have that computing the cardinality of t modulo N where , is sufficient for determining t, and thus . While there is no efficient way to compute t(mod N) directly for general N, it is possible to compute t(mod l) for l a small prime, rather efficiently. We choose S = {l_{1},l_{2},...,l_{ r}} to be a set of distinct primes such that . Given t(mod l)_{i} for all , the Chinese remainder theorem allows us to compute t(mod N).
In order to compute t(mod l) for a prime , we make use of the theory of the Frobenius endomorphism φ and division polynomials. Note that considering primes is no loss since we can always pick a bigger prime to take its place to ensure the product is big enough. In any case Schoof's algorithm is most frequently used in addressing the case q = p since there are more efficient, so called p adic algorithms for small characteristic fields.
Given the elliptic curve E defined over we consider points on E over , the algebraic closure of ; i.e. we allow points with coordinates in . The Frobenius endomorphism of over extends to the elliptic curve by .
This map is the identity on and one can extend it to the point at infinity O, making it a group morphism from to itself.
The Frobenius endomorphism satisfies a quadratic polynomial which is linked to the cardinality of by the following theorem:
Theorem: The Frobenius endomorphism given by φ satisfies the characteristic equation
φ^{2} − tφ + q = 0, where
Thus we have for all that , where + denotes addition on the elliptic curve and q(x,y) and t(x^{q},y^{ q}) denote scalar multiplication of (x,y) by q and of (x^{q},y^{ q}) by t.
One could try to symbolically compute these points , (x^{q},y^{ q}) and q(x,y) as functions in the coordinate ring of E and the search for a value of t which satisfies the equation. However, the degrees get very large and this approach is impractical.
Schoof's idea was to carry out this computation restricted to points of order l for various small primes l Fixing an odd prime l, we now move on to solving the problem of determining t_{l}, defined as t(mod l), for a given prime . If a point (x,y) is in the ltorsion subgroup , then where is the unique integer such that and . Note that φ(O) = O and that for any integer r we have rφ(P) = φ(rP). Thus φ(P) will have the same order as P. Thus for (x,y) belonging to E[l], we also have if . Hence we have reduced our problem to solving the equation
where and have integer values in [ − (l − 1) / 2,(l − 1) / 2].
The lth division polynomial is such that its roots are precisely the x coordinates of points of order l. Thus, to restrict the computatio of to the ltorsion points means computing these expressions as functions in the coordinate ring of E and modulo the lth division polynomial. I.e. we are working in . This means in particular that the degree of X and Y defined via is at most 1 in y and at most (l^{2} − 3) / 2 in x.
The scalar multiplication can be done either by doubleandadd methods or by using the th division polynomial. The latter approach gives:
where ψ_{n} is the nth division polynomial. Note that is a function in x only and denote it by θ(x).
We must split the problem into two cases: the case in which , and the case in which . Note that these equalities are checked modulo ψ_{l}.
By using the addition formula for the group we obtain:
Note that this computation fails in case the assumption of inequality was wrong.
We are now able to use the xcoordinate to narrow down the choice of to two possibilities, namely the positive and negative case. Using the ycoordinate one later determines which of the two cases holds.
We first show that X is a function in x alone. Consider . Since q^{2} − 1 is even, by replacing y^{2} by x^{3} + Ax + B, we rewrite the expression as and have that
Now if for one then satisfies for all ltorsion points P.
As mentioned earlier, using Y and we are now able to determine which of the two values of ( or ) works. This gives the value of . Schoof's algorithm stores the values of in a variable t_{l} for each prime l considered.
We begin with the assumption that . Since l is an odd prime it cannot be that and thus . The characteristic equation yields that . And consequently that . This implies that q is a square modulo l. Let . Compute wφ(x,y) in and check whether . If so, t_{l} is depending on the ycoordinate.
If q turns out not to be a square modulo l or if the equation does not hold for any of w and − w, our assumption that is false, thus . The characteristic equation gives t_{l} = 0.
If you recall, our initial considerations omit the case of l = 2. Since we assume q to be odd, and in particular, if and only if has an element of order 2. By definition of addition in the group, any element of order 2 must be of the form (x_{0},0). Thus if and only if the polynomial x^{3} + Ax + B has a root in , if and only if .
Note that since the set S was chosen so that , by Hasse's theorem, we in fact know precisely.
Most of the computation is taken by the evaluation of φ(P) and φ^{2}(P), for each prime l, that is computing x^{q}, y^{q}, , for each prime l. This involves exponentiation in the ring and requires O(logq) multiplications. Since the degree of ψ_{l} is , each element in the ring is a polynomial of degree O(l^{2}). By the prime number theorem, we have around O(logq) primes of size O(logq) giving that l is O(logq) and we obtain that O(l^{2}) = O(log^{2}q). Thus each multiplication in the ring R requires O(log^{4}q) multiplications in which in turn requires O(log^{2}q) bit operations. In total, the number of bit operations for each prime l is O(log^{7}q). Given that this computation needs to be carried out for each of the O(logq) primes, the total complexity of Schoof's algorithm turns out to be O(log^{8}q). Note that fast polynomial arithmetic reduces the costs down to O(log^{5}q).
In the 1990s, Noam Elkies, followed by A. O. L. Atkin, devised improvements to Schoof's basic algorithm by restricting the set of primes considered before to primes of a certain kind. These came to be called Elkies primes and Atkin primes respectively. A prime l is called an Elkies prime if the characteristic equation: φ^{2} − tφ + q = 0 splits over , while an Atkin prime is a prime that is not an Elkies prime. 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 SchoofElkiesAtkin 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. Once we have determined which case we are in, instead of using division polynomials, we proceed by working modulo the modular polynomials f_{l} which have a lower degree than the corresponding division polynomial ψ_{l} (degree O(l) rather than O(l^{2})). This results in a further reduction in the running time, giving us an algorithm more efficient than Schoof's, with complexity O(log^{6}q) for standard arithmetic and O(log^{4}q).
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 noncommercial use. Note that (unmodified) programs may be used to generate curves for commercial use. There are

