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

be an elliptic curve an elliptic curve can be given by a (short) Weierstrass equation

satisfying the curve equation and a point at infinity. Using the group law forms an abelian group makes use of Hasse's theorem on elliptic curves along with the Chinese remainder theorem and division polynomials.

Hasse's theorem

satisfies

, the Chinese remainder theorem.

and division polynomials adic algorithms for small-characteristic fields.

The Frobenius endomorphism

, the algebraic closure. The Frobenius endomorphism.

, making it a group morphism to itself.

by the following theorem:

Theorem: satisfies the characteristic equation

.

as functions in the coordinate ring which satisfies the equation. However, the degrees get very large and this approach is impractical.

-torsion subgroup. Hence we have reduced our problem to solving the equation

.

Computation modulo primes

The th division polynomial is such that its roots are precisely the coordinates of points of order to the -torsion points means computing these expressions as functions in the coordinate ring of and modulo the . This means in particular that the degree of and is at most 1 in in .

can be done either by double-and-addth division polynomial. The latter approach gives:

is the is a function in .

.

(x^{q^{2}}, y^{q^{2}}) \neq \pm \bar{q}(x, y)

By using the addition formula we obtain:

Note that this computation fails in case the assumption of inequality was wrong.

We are now able to use the to two possibilities, namely the positive and negative case. Using the -coordinate one later determines which of the two cases holds.

We first show that is a function in , we rewrite the expression as

and have that

satisfies

for all -torsion points .

As mentioned earlier, using for each prime considered.

(x^{q^{2}}, y^{q^{2}}) = \pm \bar{q}(x, y)

. Since . This implies that is a square modulo depending on the y-coordinate.

If turns out not to be a square modulo or if the equation does not hold for any of .

l = 2

. Since we assume .

The algorithm

    Input:
E = y^{2}-x^{3}-Ax-B.
        2. An integer qF_qq=p^{b}, b \ge 1.
    Output:
        The number of points of EF_q.
    Choose a set of odd primes S not containing p N=\prod_{l\in S} l > 4\sqrt{q}.
    Putt_2=0 if\gcd(x^{q}-x, x^{3} + Ax + B)\neq 1, elset_2=1.
    \psi_l. 
    All computations in the loop below are performed \mathbb{F}_{q}[x,y]/(y^{2}-x^{3}-Ax-B, \psi_{l}).
    Forl \in S do:
        Let\bar{q} be the unique integer q \equiv \bar{q}  \pmod l\mid \bar{q} \mid< l/2.
        (x^{q}, y^{q})(x^{q^{2}}, y^{q^{2}})(x_{\bar{q}},y_{\bar{q}}).   
        ifx^{q^{2}}\neq x_{\bar{q}} then
            (X,Y).
            for1\leq \bar{t} \leq (l-1)/2 do:
                ifX = x^{q} _ {\bar{t}} then
                    ifY = y^{q} _ {\bar{t}} then
                        t_{l}=\bar{t};
                    else
                        t_{l}=-\bar{t}.
        else if q is a square modulo l then
            compute wq\equiv w^{2} \pmod l
            w(x^{q}, y^{q})
            ifw(x^{q}, y^{q})=(x^{q^{2}}, y^{q^{2}}) then
                t_l=2w
            else ifw(x^{q}, y^{q})=(x^{q^{2}}, -y^{q^{2}}) then
                t_l=-2w
            else
                t_{l}=0
        else
            t_{l}=0
    Use the Chinese Remainder TheoremChinese Remainder Theorem to compute t modulo N
t \equiv t_{l} \pmod ll \in S.
q+1-t.

Complexity

. By the prime number theorem.

Improvements to Schoof's algorithm

In the 1990s, Noam Elkies, followed by A. O. L. Atkin, 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. For efficient implementation, probabilistic root-finding algorithms are used, which makes this a Las Vegas algorithm 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

Several algorithms were implemented in C++ by Mike Scott. 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.

• Schoof's algorithm implementation.

See also

• Elliptic curve cryptography

• Counting points on elliptic curves

• Division Polynomials

• Frobenius endomorphism

References

• 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

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