Schoof's algorithm is an efficient algorithm to count points onelliptic curves overfinite fields. The algorithm has applications inelliptic curve cryptography where it is important to know the number of points to judge the difficulty of solving thediscrete logarithm problem in thegroup of points on an elliptic curve.

The algorithm was published byRené Schoof in 1985 and it was a theoretical breakthrough, as it was the first deterministic polynomial time algorithm forcounting points on elliptic curves. Before Schoof's algorithm, approaches to counting points on elliptic curves such as the naive andbaby-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.

Let${\displaystyle E}$ be anelliptic curve defined over the finite field${\displaystyle {\mathbb{F}}_q}$, where${\displaystyle q=p^n}$ for${\displaystyle p}$ a prime and${\displaystyle n}$ an integer${\displaystyle \ge 1}$. Over a field of characteristic${\displaystyle \ne 2,3}$ an elliptic curve can be given by a (short) Weierstrass equation

${\displaystyle y^2=x^3+Ax+B}$

with${\displaystyle A,B\in {\mathbb{F}}_q}$. The set of points defined over${\displaystyle {\mathbb{F}}_q}$ consists of the solutions${\displaystyle (a,b)\in {\mathbb{F}}_q^2}$ satisfying the curve equation and apoint at infinity${\displaystyle O}$. Using thegroup law on elliptic curves restricted to this set one can see that this set${\displaystyle E({\mathbb{F}}_q)}$ forms anabelian group, with${\displaystyle O}$ acting as the zero element.In order to count points on an elliptic curve, we compute the cardinality of${\displaystyle E({\mathbb{F}}_q)}$.Schoof's approach to computing the cardinality${\displaystyle \mathrm{\#}E({\mathbb{F}}_q)}$ makes use ofHasse's theorem on elliptic curves along with theChinese remainder theorem anddivision polynomials.

Hasse's theorem states that if${\displaystyle E/{\mathbb{F}}_q}$ is an elliptic curve over the finite field${\displaystyle {\mathbb{F}}_q}$, then${\displaystyle \mathrm{\#}E({\mathbb{F}}_q)}$ satisfies

${\displaystyle \mid q+1-\mathrm{\#}E({\mathbb{F}}_q)\mid \le 2\sqrt{q}.}$

This powerful result, given by Hasse in 1934, simplifies our problem by narrowing down${\displaystyle \mathrm{\#}E({\mathbb{F}}_q)}$ to a finite (albeit large) set of possibilities. Defining${\displaystyle t}$ to be${\displaystyle q+1-\mathrm{\#}E({\mathbb{F}}_q)}$, and making use of this result, we now have that computing the value of${\displaystyle t}$ modulo${\displaystyle N}$ where${\displaystyle N>4\sqrt{q}}$, is sufficient for determining${\displaystyle t}$, and thus${\displaystyle \mathrm{\#}E({\mathbb{F}}_q)}$. While there is no efficient way to compute${\displaystyle t(\mathrm{mod}N)}$ directly for general${\displaystyle N}$, it is possible to compute${\displaystyle t(\mathrm{mod}l)}$ for${\displaystyle l}$ a small prime, rather efficiently. We choose${\displaystyle S=\{l_1,l_2,...,l_r\}}$ to be a set of distinct primes such that${\displaystyle \prod l_i=N>4\sqrt{q}}$. Given${\displaystyle t(\mathrm{mod}{l}_i)}$ for all${\displaystyle l_i\in S}$, theChinese remainder theorem allows us to compute${\displaystyle t(\mathrm{mod}N)}$.

In order to compute${\displaystyle t(\mathrm{mod}l)}$ for a prime${\displaystyle l\ne p}$, we make use of the theory of the Frobenius endomorphism${\displaystyle \varphi }$ anddivision polynomials. Note that considering primes${\displaystyle l\ne p}$ 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${\displaystyle q=p}$ since there are more efficient, so called${\displaystyle p}$ adic algorithms for small-characteristic fields.

Given the elliptic curve${\displaystyle E}$ defined over${\displaystyle {\mathbb{F}}_q}$ we consider points on${\displaystyle E}$ over${\displaystyle {\overline{\mathbb{F}}}_q}$, thealgebraic closure of${\displaystyle {\mathbb{F}}_q}$; i.e. we allow points with coordinates in${\displaystyle {\overline{\mathbb{F}}}_q}$. TheFrobenius endomorphism of${\displaystyle {\overline{\mathbb{F}}}_q}$ over${\displaystyle {\mathbb{F}}_q}$ extends to the elliptic curve by${\displaystyle \varphi :(x,y)\mapsto (x^q,y^q)}$.

This map is the identity on${\displaystyle E({\mathbb{F}}_q)}$ and one can extend it to the point at infinity${\displaystyle O}$, making it agroup morphism from${\displaystyle E({\overline{\mathbb{F}}}_q)}$ to itself.

The Frobenius endomorphism satisfies a quadratic polynomial which is linked to the cardinality of${\displaystyle E({\mathbb{F}}_q)}$ by the following theorem:

Theorem: The Frobenius endomorphism given by${\displaystyle \varphi }$ satisfies the characteristic equation

${\displaystyle {\varphi }^2-t\varphi +q=0,}$ where${\displaystyle t=q+1-\mathrm{\#}E({\mathbb{F}}_q)}$

Thus we have for all${\displaystyle P=(x,y)\in E}$ that${\displaystyle (x^{q^2},y^{q^2})+q(x,y)=t(x^q,y^q)}$, where + denotes addition on the elliptic curve and${\displaystyle q(x,y)}$ and${\displaystyle t(x^q,y^q)}$denote scalar multiplication of${\displaystyle (x,y)}$ by${\displaystyle q}$ and of${\displaystyle (x^q,y^q)}$ by${\displaystyle t}$.

One could try to symbolically compute these points${\displaystyle (x^{q^2},y^{q^2})}$,${\displaystyle (x^q,y^q)}$ and${\displaystyle q(x,y)}$ as functions in thecoordinate ring${\displaystyle {\mathbb{F}}_q[x,y]/(y^2-x^3-Ax-B)}$ of${\displaystyle E}$and then search for a value of${\displaystyle 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${\displaystyle l}$ for various small primes${\displaystyle l}$.Fixing an odd prime${\displaystyle l}$, we now move on to solving the problem of determining${\displaystyle t_l}$, defined as${\displaystyle t(\mathrm{mod}l)}$, for a given prime${\displaystyle l\ne 2,p}$. If a point${\displaystyle (x,y)}$ is in the${\displaystyle l}$-torsion subgroup${\displaystyle E[l]=\{P\in E(\overline{{\mathbb{F}}_q})\mid lP=O\}}$, then${\displaystyle qP=\overline{q}P}$ where${\displaystyle \overline{q}}$ is the unique integer such that${\displaystyle q\equiv \overline{q}(\mathrm{mod}l)}$ and. Note that${\displaystyle \varphi (O)=O}$ and that for any integer${\displaystyle r}$ we have${\displaystyle r\varphi (P)=\varphi (rP)}$. Thus${\displaystyle \varphi (P)}$ will have the same order as${\displaystyle P}$. Thus for${\displaystyle (x,y)}$ belonging to${\displaystyle E[l]}$, we also have${\displaystyle t(x^q,y^q)=\overline{t}(x^q,y^q)}$ if${\displaystyle t\equiv \overline{t}(\mathrm{mod}l)}$. Hence we have reduced our problem to solving the equation

${\displaystyle (x^{q^2},y^{q^2})+\overline{q}(x,y)\equiv \overline{t}(x^q,y^q),}$

where${\displaystyle \overline{t}}$ and${\displaystyle \overline{q}}$ have integer values in${\displaystyle [-(l-1)/2,(l-1)/2]}$.

Thelthdivision polynomial is such that its roots are precisely thex coordinates of points of orderl. Thus, to restrict the computation of${\displaystyle (x^{q^2},y^{q^2})+\overline{q}(x,y)}$ to thel-torsion points means computing these expressions as functions in the coordinate ring ofEand modulo thelth division polynomial. I.e. we are working in${\displaystyle {\mathbb{F}}_q[x,y]/(y^2-x^3-Ax-B,{\psi }_l)}$. This means in particular that the degree ofX andY defined via${\displaystyle (X(x,y),Y(x,y)):=(x^{q^2},y^{q^2})+\overline{q}(x,y)}$ is at most 1 iny and at most${\displaystyle (l^2-3)/2}$inx.

The scalar multiplication${\displaystyle \overline{q}(x,y)}$ can be done either bydouble-and-add methods or by using the${\displaystyle \overline{q}}$th division polynomial. The latter approach gives:

${\displaystyle \overline{q}(x,y)=(x_{\overline{q}},y_{\overline{q}})=\left(x-\frac{{\psi }_{\overline{q}-1}{\psi }_{\overline{q}+1}}{{\psi }_{\overline{q}}^2},\frac{{\psi }_{2\overline{q}}}{2{\psi }_{\overline{q}}^4}\right)}$

where${\displaystyle {\psi }_n}$ is thenth division polynomial. Note that${\displaystyle y_{\overline{q}}/y}$ is a function inx only and denote it by${\displaystyle \theta (x)}$.

We must split the problem into two cases: the case in which${\displaystyle (x^{q^2},y^{q^2})\ne \pm \overline{q}(x,y)}$, and the case in which${\displaystyle (x^{q^2},y^{q^2})=\pm \overline{q}(x,y)}$. Note that these equalities are checked modulo${\displaystyle {\psi }_l}$.

By using theaddition formula for the group${\displaystyle E({\mathbb{F}}_q)}$ we obtain:

${\displaystyle X(x,y)={\left(\frac{y^{q^2}-y_{\overline{q}}}{x^{q^2}-x_{\overline{q}}}\right)}^2-x^{q^2}-x_{\overline{q}}.}$

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

We are now able to use thex-coordinate to narrow down the choice of${\displaystyle \overline{t}}$ to two possibilities, namely the positive and negative case. Using they-coordinate one later determines which of the two cases holds.

We first show thatX is a function inx alone. Consider${\displaystyle (y^{q^2}-y_{\overline{q}}{)}^2=y^2(y^{q^2-1}-y_{\overline{q}}/y{)}^2}$.Since${\displaystyle q^2-1}$ is even, by replacing${\displaystyle y^2}$ by${\displaystyle x^3+Ax+B}$, we rewrite the expression as

${\displaystyle (x^3+Ax+B)((x^3+Ax+B{)}^{\frac{q^2-1}{2}}-\theta (x))}$

and have that

${\displaystyle X(x)\equiv (x^3+Ax+B)((x^3+Ax+B{)}^{\frac{q^2-1}{2}}-\theta (x)){mod\psi }_l(x).}$

Here, it seems not right, we throw away${\displaystyle x^{q^2}-x_{\overline{q}}}$?

Now if${\displaystyle X\equiv x_{\overline{t}}^q{mod\psi }_l(x)}$ for one${\displaystyle \overline{t}\in [0,(l-1)/2]}$ then${\displaystyle \overline{t}}$ satisfies

${\displaystyle {\varphi }^2(P)\mp \overline{t}\varphi (P)+\overline{q}P=O}$

for alll-torsion pointsP.

As mentioned earlier, usingY and${\displaystyle y_{\overline{t}}^q}$ we are now able to determine which of the two values of${\displaystyle \overline{t}}$ (${\displaystyle \overline{t}}$ or${\displaystyle -\overline{t}}$) works. This gives the value of${\displaystyle t\equiv \overline{t}(\mathrm{mod}l)}$. Schoof's algorithm stores the values of${\displaystyle \overline{t}(\mathrm{mod}l)}$ in a variable${\displaystyle t_l}$ for each primel considered.

We begin with the assumption that${\displaystyle (x^{q^2},y^{q^2})=\overline{q}(x,y)}$. Sincel is an odd prime it cannot be that${\displaystyle \overline{q}(x,y)=-\overline{q}(x,y)}$ and thus${\displaystyle \overline{t}\ne 0}$. The characteristic equation yields that${\displaystyle \overline{t}\varphi (P)=2\overline{q}P}$. And consequently that${\displaystyle {\overline{t}}^2\overline{q}\equiv (2q{)}^2(\mathrm{mod}l)}$. This implies thatq is a square modulol. Let${\displaystyle q\equiv w^2(\mathrm{mod}l)}$. Compute${\displaystyle w\varphi (x,y)}$ in${\displaystyle {\mathbb{F}}_q[x,y]/(y^2-x^3-Ax-B,{\psi }_l)}$ and check whether${\displaystyle \overline{q}(x,y)=w\varphi (x,y)}$. If so,${\displaystyle t_l}$ is${\displaystyle \pm 2w(\mathrm{mod}l)}$ depending on the y-coordinate.

Ifq turns out not to be a square modulol or if the equation does not hold for any ofw and${\displaystyle -w}$, our assumption that${\displaystyle (x^{q^2},y^{q^2})=+\overline{q}(x,y)}$ is false, thus${\displaystyle (x^{q^2},y^{q^2})=-\overline{q}(x,y)}$. The characteristic equation gives${\displaystyle t_l=0}$.

If you recall, our initial considerations omit the case of${\displaystyle l=2}$. Since we assumeq to be odd,${\displaystyle q+1-t\equiv t(\mathrm{mod}2)}$ and in particular,${\displaystyle t_2\equiv 0(\mathrm{mod}2)}$ if and only if${\displaystyle E({\mathbb{F}}_q)}$ has an element of order 2. By definition of addition in the group, any element of order 2 must be of the form${\displaystyle (x_0,0)}$. Thus${\displaystyle t_2\equiv 0(\mathrm{mod}2)}$ if and only if the polynomial${\displaystyle x^3+Ax+B}$ has a root in${\displaystyle {\mathbb{F}}_q}$, if and only if${\displaystyle gcd(x^q-x,x^3+Ax+B)\ne 1}$.

    Input:        1. An elliptic curve${\displaystyle E=y^2-x^3-Ax-B}$.        2. An integerq for a finite field${\displaystyle F_q}$ with${\displaystyle q=p^b,b\ge 1}$.    Output:        The number of points ofE over${\displaystyle F_q}$.    Choose a set of odd primesS not containingpsuch that${\displaystyle N=\prod _{l\in S}l>4\sqrt{q}.}$Put${\displaystyle t_2=0}$if${\displaystyle gcd(x^q-x,x^3+Ax+B)\ne 1}$,else${\displaystyle t_2=1}$.Compute the division polynomial${\displaystyle {\psi }_l}$.     All computations in the loop below are performedin the ring${\displaystyle {\mathbb{F}}_q[x,y]/(y^2-x^3-Ax-B,{\psi }_l).}$For${\displaystyle l\in S}$do:Let${\displaystyle \overline{q}}$ be the unique integersuch that${\displaystyle q\equiv \overline{q}(\mathrm{mod}l)}$ and.Compute${\displaystyle (x^q,y^q)}$,${\displaystyle (x^{q^2},y^{q^2})}$ and${\displaystyle (x_{\overline{q}},y_{\overline{q}})}$.if${\displaystyle x^{q^2}\ne x_{\overline{q}}}$thenCompute${\displaystyle (X,Y)}$.for${\displaystyle 1\le \overline{t}\le (l-1)/2}$do:if${\displaystyle X=x_{\overline{t}}^q}$thenif${\displaystyle Y=y_{\overline{t}}^q}$then${\displaystyle t_l=\overline{t}}$;else${\displaystyle t_l=-\overline{t}}$.else ifq is a square modulolthencomputew with${\displaystyle q\equiv w^2(\mathrm{mod}l)}$compute${\displaystyle w(x^q,y^q)}$if${\displaystyle w(x^q,y^q)=(x^{q^2},y^{q^2})}$then${\displaystyle t_l=2w}$else if${\displaystyle w(x^q,y^q)=(x^{q^2},-y^{q^2})}$then${\displaystyle t_l=-2w}$else${\displaystyle t_l=0}$else${\displaystyle t_l=0}$    Use theChinese Remainder Theorem to computet moduloN        from the equations${\displaystyle t\equiv t_l(\mathrm{mod}l)}$, where${\displaystyle l\in S}$.    Output${\displaystyle q+1-t}$.

Most of the computation is taken by the evaluation of${\displaystyle \varphi (P)}$ and${\displaystyle {\varphi }^2(P)}$, for each prime${\displaystyle l}$, that is computing${\displaystyle x^q}$,${\displaystyle y^q}$,${\displaystyle x^{q^2}}$,${\displaystyle y^{q^2}}$ for each prime${\displaystyle l}$. This involves exponentiation in the ring${\displaystyle R={\mathbb{F}}_q[x,y]/(y^2-x^3-Ax-B,{\psi }_l)}$ and requires${\displaystyle O(\log q)}$ multiplications. Since the degree of${\displaystyle {\psi }_l}$ is${\displaystyle \frac{l^2-1}{2}}$, each element in the ring is a polynomial of degree${\displaystyle O(l^2)}$. By theprime number theorem, there are around${\displaystyle O(\log q)}$ primes of size${\displaystyle O(\log q)}$, giving that${\displaystyle l}$ is${\displaystyle O(\log q)}$ and we obtain that${\displaystyle O(l^2)=O({\log }^{2}q)}$. Thus each multiplication in the ring${\displaystyle R}$ requires${\displaystyle O({\log }^{4}q)}$ multiplications in${\displaystyle {\mathbb{F}}_q}$ which in turn requires${\displaystyle O({\log }^{2}q)}$ bit operations. In total, the number of bit operations for each prime${\displaystyle l}$ is${\displaystyle O({\log }^{7}q)}$. Given that this computation needs to be carried out for each of the${\displaystyle O(\log q)}$ primes, the total complexity of Schoof's algorithm turns out to be${\displaystyle O({\log }^{8}q)}$. Using fast polynomial and integer arithmetic reduces this to${\displaystyle \tilde{O}({\log }^{5}q)}$.

In the 1990s,Noam Elkies, followed byA. O. L. Atkin, devised improvements to Schoof's basic algorithm by restricting the set of primes${\displaystyle S=\{l_1,\dots ,l_s\}}$ considered before to primes of a certain kind. These came to be called Elkies primes and Atkin primes respectively. A prime${\displaystyle l}$ is called an Elkies prime if the characteristic equation:${\displaystyle {\varphi }^2-t\varphi +q=0}$ splits over${\displaystyle {\mathbb{F}}_l}$, 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 theSchoof–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 ofmodular forms and an interpretation ofelliptic curves over the complex numbers as lattices. Once we have determined which case we are in, instead of usingdivision polynomials, we are able to work with a polynomial that has lower degree than the corresponding division polynomial:${\displaystyle O(l)}$ rather than${\displaystyle O(l^2)}$. For efficient implementation, probabilistic root-finding algorithms are used, which makes this aLas Vegas algorithm rather than a deterministic algorithm.Under the heuristic assumption that approximately half of the primes up to an${\displaystyle O(\log q)}$ bound are Elkies primes, this yields an algorithm that is more efficient than Schoof's, with an expected running time of${\displaystyle O({\log }^{6}q)}$ using naive arithmetic, and${\displaystyle \tilde{O}({\log }^{4}q)}$ 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 theGRH.

Several algorithms were implemented inC++ by Mike Scott and are available withsource code. The implementations are free (no terms, no conditions), and make use of theMIRACL library which is distributed under theAGPLv3.

• Schoof's algorithmimplementation for${\displaystyle E({\mathbb{F}}_p)}$ with prime${\displaystyle p}$.
• Schoof's algorithmimplementation for${\displaystyle E({\mathbb{F}}_{2^m})}$.

• Elliptic curve cryptography
• Counting points on elliptic curves
• Division Polynomials
• Frobenius endomorphism

• R. Schoof: Elliptic Curves over Finite Fields and the Computation of Square Roots mod p. Math. Comp., 44(170):483–494, 1985. Available athttp://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 athttp://www.mat.uniroma2.it/~schoof/ctg.pdf
• G. Musiker: Schoof's Algorithm for Counting Points on${\displaystyle E({\mathbb{F}}_q)}$. Available athttp://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 athttp://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

• Asymmetric-key algorithms
• Elliptic curve cryptography
• Elliptic curves
• Group theory
• Finite fields
• Number theory

• Articles with short description
• Short description matches Wikidata