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

Introduction

edit

Let   be an elliptic curve defined over the finite field  , where   for   a prime and   an integer  . Over a field of characteristic   an elliptic curve can be given by a (short) Weierstrass equation

 

with  . The set of points defined over   consists of the solutions   satisfying the curve equation and a point at infinity  . Using the group law on elliptic curves restricted to this set one can see that this set   forms an abelian group, with   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

edit

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   to be  , and making use of this result, we now have that computing the value of   modulo   where  , is sufficient for determining  , and thus  . While there is no efficient way to compute   directly for general  , it is possible to compute   for   a small prime, rather efficiently. We choose   to be a set of distinct primes such that  . Given   for all  , the Chinese remainder theorem allows us to compute  .

In order to compute   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   since there are more efficient, so called   adic algorithms for small-characteristic fields.

The Frobenius endomorphism

edit

Given the elliptic curve   defined over   we consider points on   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  , 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

  where  

Thus we have for all   that  , where + denotes addition on the elliptic curve and   and   denote scalar multiplication of   by   and of   by  .

One could try to symbolically compute these points  ,   and   as functions in the coordinate ring   of   and then search for a value of   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   for various small primes  . Fixing an odd prime  , we now move on to solving the problem of determining  , defined as  , for a given prime  . If a point   is in the  -torsion subgroup  , then   where   is the unique integer such that   and  . Note that   and that for any integer   we have  . Thus   will have the same order as  . Thus for   belonging to  , we also have   if  . Hence we have reduced our problem to solving the equation

 

where   and   have integer values in  .

Computation modulo primes

edit

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. 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   in x.

The scalar multiplication   can be done either by double-and-add methods or by using the  th division polynomial. The latter approach gives:

 

where   is the nth division polynomial. Note that   is a function in x only and denote it by  .

We must split the problem into two cases: the case in which  , and the case in which  . Note that these equalities are checked modulo  .

Case 1:  

edit

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 x-coordinate to narrow down the choice of   to two possibilities, namely the positive and negative case. Using the y-coordinate one later determines which of the two cases holds.

We first show that X is a function in x alone. Consider  . Since   is even, by replacing   by  , we rewrite the expression as

 

and have that

 

Here, it seems not right, we throw away  ?

Now if   for one   then   satisfies

 

for all l-torsion 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   for each prime l considered.

Case 2:  

edit

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   in   and check whether  . If so,   is   depending on the y-coordinate.

If q turns out not to be a square modulo l or if the equation does not hold for any of w and  , our assumption that   is false, thus  . The characteristic equation gives  .

Additional case  

edit

If you recall, our initial considerations omit the case of  . 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  . Thus   if and only if the polynomial   has a root in  , if and only if  .

The algorithm

edit
    Input:
        1. An elliptic curve  .
        2. An integer q for a finite field   with  .
    Output:
        The number of points of E over  .
    Choose a set of odd primes S not containing p such that  
    Put   if  , else  .
    Compute the division polynomial  . 
    All computations in the loop below are performed in the ring  
    For   do:
        Let   be the unique integer such that    and  .
        Compute  ,   and  .   
        if   then
            Compute  .
            for   do:
                if   then
                    if   then
                         ;
                    else
                         .
        else if q is a square modulo l then
            compute w with  
            compute  
            if   then
                 
            else if   then
                 
            else
                 
        else
             
    Use the Chinese Remainder Theorem to compute t modulo N
        from the equations  , where  .
    Output  .

Complexity

edit

Most of the computation is taken by the evaluation of   and  , for each prime  , that is computing  ,  ,  ,   for each prime  . This involves exponentiation in the ring   and requires   multiplications. Since the degree of   is  , each element in the ring is a polynomial of degree  . By the prime number theorem, there are around   primes of size  , giving that   is   and we obtain that  . Thus each multiplication in the ring   requires   multiplications in   which in turn requires   bit operations. In total, the number of bit operations for each prime   is  . Given that this computation needs to be carried out for each of the   primes, the total complexity of Schoof's algorithm turns out to be  . Using fast polynomial and integer arithmetic reduces this to  .

Improvements to Schoof's algorithm

edit

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   is called an Elkies prime if the characteristic equation:   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 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. Once we have determined which case we are in, instead of using division polynomials, we are able to work with a polynomial that has lower degree than the corresponding division polynomial:   rather than  . For efficient implementation, probabilistic root-finding algorithms are used, which makes this a Las Vegas algorithm rather than a deterministic algorithm. 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   using naive arithmetic, and   using fast arithmetic. Although this heuristic assumption is known to hold for most elliptic curves, it is not known to hold in every case, even under the GRH.

Implementations

edit

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.

  • Schoof's algorithm implementation for   with prime  .
  • Schoof's algorithm implementation for  .

See also

edit

References

edit
  • R. Schoof: Elliptic Curves over Finite Fields and the Computation of Square Roots mod p. Math. Comp., 44(170):483–494, 1985. Available at http://www.mat.uniroma2.it/~schoof/ctpts.pdf
  • R. Schoof: Counting Points on Elliptic Curves over Finite Fields. J. Theor. Nombres Bordeaux 7:219–254, 1995. Available at http://www.mat.uniroma2.it/~schoof/ctg.pdf
  • G. Musiker: Schoof's Algorithm for Counting Points on  . Available at http://www.math.umn.edu/~musiker/schoof.pdf
  • V. Müller : Die Berechnung der Punktanzahl von elliptischen kurven über endlichen Primkörpern. Master's Thesis. Universität des Saarlandes, Saarbrücken, 1991. Available at http://lecturer.ukdw.ac.id/vmueller/publications.php
  • A. Enge: Elliptic Curves and their Applications to Cryptography: An Introduction. Kluwer Academic Publishers, Dordrecht, 1999.
  • L. C. Washington: Elliptic Curves: Number Theory and Cryptography. Chapman & Hall/CRC, New York, 2003.
  • N. Koblitz: A Course in Number Theory and Cryptography, Graduate Texts in Math. No. 114, Springer-Verlag, 1987. Second edition, 1994