Schoof's algorithm

Schoof's Algorithm is an important tool of Elliptic Curve Cryptography that provides us with an efficient way of counting points on elliptic curves. Published as a paper by Rene Schoof in 1985, the algorithm was a theoretical break through, as it was the first deterministic polynomial time algorithm.

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

In order to count points on elliptic curve, we compute the cardinality of $E(\mathbb {F} _{q})$, the group of an elliptic curve $E(\mathbb {F} _{q})$ over a finite field $\mathbb {F} _{q}$ of characteristic $p$. Schoof's approach to compute the cardinality $\sharp E(\mathbb {F} _{q})$ makes use of Hasse's theorem along with the Chinese Remainder Theorem and Division Polynomials.

We treat an elliptic curve $E(\mathbb {F} _{q})$ as the zero locus of an algebraic equation of a special form, commonly known as the Weierstrass form. Over a field of characteristic $\neq 2,3$, this equation can be written as

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

The set of points defined over $\mathbb {F} _{q}$ satisfying this equation, together with an additional `point at infinity' $O$, form the abelian group $E(\mathbb {F} _{q})$, with $O$ acting as the zero element.

Hasse's Theorem

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

$\mid q+1-\sharp E(\mathbb {F} _{q})\mid \leq 2{\sqrt {q}}.$

This powerful result, given by Hasse in 1934, simplifies our problem by narrowing down $\sharp E(\mathbb {F} _{q})$ to a finite (albeit large) set of possibilities. Defining $t$ to be $q+1-\sharp E(\mathbb {F} _{q})$, and making use of this result, we now have that computing the cardinality of $t$ modulo $N$ where $N>4{\sqrt {q}}$, is sufficient for determining $t$, and thus $\sharp E(\mathbb {F} _{q})$. While there is no efficient way to compute $t{\pmod {N}}$ directly for general $N$, it is possible to compute $t{\pmod {l}}$ for $l$ prime, rather efficiently. We choose $S$ to be a set of distinct primes such that $\prod l=N>4{\sqrt {q}}$. Given $t{\pmod {l}}$ for all $l\in S$, the Chinese Remainder Theorem allows us to compute $t{\pmod {N}}$.

In order to compute $t{\pmod {l}}$ for a prime $l\neq p$, we make use of the theory of the Frobenius endomorphism $\phi$ and Division Polynomials. Note that considering primes $l\neq 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 $q=p$ since there are more efficient algorithms for small characteristic fields.

The Frobenius Endomorphism

Given the elliptic curve $E(\mathbb {F} _{q})$ we consider $E$ to be the curve with same defining equation as $E(\mathbb {F} _{q})$, but now allowing points with coordinates in ${\overline {\mathbb {F} _{q}}}$, the algebraic closure of $\mathbb {F} _{q}$. Given curve $E$, there exists a map (the Frobenius endomorphism) given by $\phi :(x,y)\mapsto (x^{q},y^{q})$

This map is the identity on $E(\mathbb {F} _{q})$ and one can extend it to the point at infinity $O$, making it a group morphism from $E({\bar {\mathbb {F} _{q}}})$ to itself.

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

Theorem: The Frobenius endomorphism given by $\phi$ satisfies the characteristic equation

$\phi ^{2}-t\phi +q=0$ where $t=q+1-\sharp E(\mathbb {F} _{q})$

Thus we have for all $P=(x,y)\in E$, $(x^{q^{2}},y^{q^{2}})+q(x,y)=t(x^{q},y^{q})$, 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$.

Fixing $l$, we now move on to solving the problem of determining $t_{l}$, defined as $t{\pmod {l}}$, for a given prime $l\neq 2,p$. If a point $(x,y)$ is in the torsion subgroup $E[l]=\{P\in E({\bar {\mathbb {F} _{q}}})\mid lP=O\}$, then $qP={\bar {q}}P$ where ${\bar {q}}$ is the unique integer such that $q\equiv {\bar {q}}{\pmod {l}}$ and $\mid {\bar {q}}\mid <l/2$. Being a group morphism, we have that $\phi (O)=O$ and if $r$ is an integer, then $r\phi (P)=\phi (rP)$. Thus $\phi (P)$ will have the same order as $P$. Thus for $(x,y)$ belonging to $E[l]$, we also have $t(x^{q},y^{q})={\bar {t}}(x^{q},y^{q})$ if $t\equiv {\bar {t}}{\pmod {l}}$. Hence we have reduced our problem to solving the equation

$(x^{q^{2}},y^{q^{2}})+{\bar {q}}(x,y)\equiv {\bar {t}}(x^{q},y^{q}){\pmod {l}}$

Computation modulo primes

We must now compute $(x^{q^{2}},y^{q^{2}})+{\bar {q}}(x,y)$ as a pair of rational functions $(x',y'):=(x^{q^{2}},y^{q^{2}})+{\bar {q}}(x,y)$ in terms of $x$ and $y$ (remember that we are working modulo $l$). We do so by using Division Polynomials, which lie at the heart of the remaining part of Schoof's algorithm.

We obtain:

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

where $\psi _{n}$, a function of $x$ and $y$, is the $n$th division polynomial. By replacing $y^{2}$ by $x^{3}+Ax+B$, we have that $\theta (x)=y_{\bar {q}}/y$ is an expression in $x$.

We must split the problem into two cases: the case in which $(x^{q^{2}},y^{q^{2}})\neq \pm q(x,y)$, and the case in which $(x^{q^{2}},y^{q^{2}})=\pm q(x,y)$.

Case 1: $(x^{q^{2}},y^{q^{2}})\neq \pm q(x,y)$

By using the addition formula for the group $E(\mathbb {F} _{q})$ we obtain:

$x'=\left({\frac {y^{q^{2}}-y_{\bar {q}}}{x^{q^{2}}-x_{\bar {q}}}}\right)^{2}-x^{q^{2}}-x_{\bar {q}}$

We are now able to use the $x$-coordinate to narrow down the choice of ${\bar {t}}$ 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 $(y^{q^{2}}-y_{\bar {q}})^{2}=y^{2}(y^{q^{2}-1}-y_{\bar {q}}/y)^{2}$. Since $q^{2}-1$ is even, by replacing $y^{2}$ by $x^{3}+Ax+B$, we rewrite the expression as $(x^{3}+Ax+B)((x^{3}+Ax+B)^{\frac {q^{2}-1}{2}}-\theta (x))$

Note that such a substitution would mean that we are working in the ring $\mathbb {F} _{q}[x,y]/(y^{2}-x^{3}-Ax-B)$.

Now if $x'=x_{\bar {t}}^{q}$ for one point $P=(x,y)$ in $E[l]\setminus \{O\}$ then ${\bar {t}}$ satisfies $\phi ^{2}(P)-{\bar {t}}\phi (P)+qP=O$ implying that $x'=x_{\bar {t}}^{q}$ for all points $P$ in $E[l]\setminus \{O\}$ and confirming that ${\bar {t}}=t_{l}$.

But since the roots of the $l$-th Division Polynomial $\psi _{l}$ are exactly the $x$-coordinates of the points of $E[l]\setminus \{O\}$ and are simple, we can reduce our problem to solving the equation

$x'\equiv x_{\bar {t}}^{q}{\pmod {\psi _{l}}}$ (where $\psi _{l}$ is the $l$-th division polynomial)

That is, we are now working in the ring $\mathbb {F} _{q}[x,y]/(y^{2}-x^{3}-Ax-B,\psi _{l})$.

As mentioned earlier, using the $y'$ and $y_{\bar {t}}^{q}$ we are now able to determine which of the two values of ${\bar {t}}$ (${\bar {t}}$ or $-{\bar {t}}$) works. This computation fails in case the assumption of inequality was wrong.

Case 2: $(x^{q^{2}},y^{q^{2}})=\pm q(x,y)$

We begin with the assumption that $(x^{q^{2}},y^{q^{2}})=+q(x,y)$. For a point $P$ in $E(\mathbb {F} _{q})$ satisfying this, plugging it into the characteristic equation yields that ${\bar {t}}\phi (P)=2{\bar {q}}P$. And consequently that ${\bar {t}}^{2}{\bar {q}}P\equiv (2q)^{2}P{\pmod {l}}$. This implies that $q$ is a square modulo $l$ unless ${\bar {t}}$ is $0mod\,l$. We discount the latter case as it yields a contradiction. We find $q$'s square-roots over $\mathbb {F} _{l}$. If $q\equiv w^{2}{\pmod {l}}$, we find that $t_{l}$ will be $\pm 2w$ mod $l$ depending on the y-coordinate. If $q$ turns out not to be a square modulo $l$, our assumption that $(x^{q^{2}},y^{q^{2}})=+q(x,y)$ is rendered false, forcing us to consider the case where $(x^{q^{2}},y^{q^{2}})=-q(x,y)$, in which case our argument asserts that ${\bar {t}}$ is $0\,(mod\,l)$.

As you might notice, it is possible for $q$ to be a square ${\pmod {l}}$ but $(x^{q^{2}},y^{q^{2}})=-q(x,y)$. In this case however, it suffices to check whether or not either square root $\pm w$ satisfies $\phi (P)=\pm wP$, for $P\in E[l]\setminus \{O\}$, and this amounts to checking whether or not $\gcd(numerator(x^{q}-x_{w}),\phi _{l})=1$. If it is $1$ then we are in the minus case and $t_{l}=0$; if $\neq 1$ we proceed as in the plus case with $t_{l}=\pm 2w$.

Additional Case: $l=2$

If you recall, our initial considerations omit the case of $l=2$. Since we assume $q$ to be odd, $q+1-t\equiv t{\pmod {2}}$ and in particular, $t_{2}\equiv 0{\pmod {2}}$ if and only if $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 $(x_{0},0)$. Thus $t_{2}\equiv 0{\pmod {2}}$ if and only if the polynomial $x^{3}+Ax+B$ has a root in $\mathbb {F} _{q}$, if and only if $\gcd(x^{q}-x,x^{3}+Ax+B)\neq 1$.

The Algorithm

(1) Choose a set of primes $S$, $p\notin S$ such that $N=\prod _{l\in S}l>4{\sqrt {q}}$  
(2) For $l=2$, $t_{l}=0$ if and only if $\gcd(x^{q}-x,x^{3}+Ax+B)\neq 1$  
(3) For  $l\in S\setminus \{2\}$ do  
         (a) let ${\bar {q}}$ be the unique integer such that  $q\equiv {\bar {q}}{\pmod {l}}$ and $\mid {\bar {q}}\mid <l/2$
         (b) compute $x'$ as above.   
         (c) for  $1\leq {\bar {t}}\leq (l-1)/2$ do  
                   (i)  if  $x'=x_{\bar {t}}^{q}{\pmod {\psi _{l}}}$ go to ii. . Otherwise try next value of ${\bar {t}}$. If you have unsuccesfully tried $(l-1)/2$, go to (d).  
                   (ii) if  $(y'-y_{\bar {t}}^{q})/y\equiv 0{\pmod {\psi _{l}}}$ then $t_{l}={\bar {t}}$; otherwise $t_{l}=-{\bar {t}}$  
         (d) Find $q$'s square roots modulo $l$,if they exist. If they don't exist then $t_{l}=0$. Otherwise let $q\equiv w^{2}{\pmod {l}}$  
         (e) If $\gcd(numerator(x^{q}-x_{w}),\phi _{l})=1$ $t_{l}-2w$. Otherwise $t_{l}\equiv 2w$  
(4) Use Chinese Remainder Theorem to compute $\sharp E(\mathbb {F} _{q}){\pmod {N}}$.

Note that since the set $S$ was chosen so that $N>4{\sqrt {q}}$, by Hasse's theorem, we in fact know $\sharp E(\mathbb {F} _{q})$ precisely.

Complexity of Schoof's Algorithm

Most of the computation is taken by the evaluation of $\phi (P)$ and $\phi ^{2}(P)$, for each prime $l$, that is computing $x^{q}$, $y^{q}$, $x^{q^{2}}$, $y^{q^{2}}$ for each prime $l$. This involves exponentiation in the ring $R=\mathbb {F} _{q}[x,y]/(y^{2}-x^{3}-Ax-B,\psi _{l})$ and requires $O(\log q)$ multiplications. Since the degree of $\psi _{l}$ is ${\frac {l^{2}-1}{2}}$, each element in the ring is a polynomial of degree $O(l^{2})$, 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 $\mathbb {F} _{q}$ 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)$. By the prime number theorem*, we have around $O(\log q)$ primes, and thus the total complexity of Schoof's algorithm turns out to be $O(\log ^{7}q)\cdot O(\log q)=O(\log ^{8}q)$.

Improvements to Schoof's Algorithm

In the 1990s, Elkies, followed by Atkin devised improvements to Schoof's basic algorithm by restricting the set of primes $S=\{l_{1},\ldots ,l_{s}\}$ 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: $\phi ^{2}-t\phi +q=0$ splits over $\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 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 proceed by working modulo the modular polynomials $f_{l}$ which have a lower degree than the corresponding division polynomial $\psi _{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)$.

Implementations

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 non-commercial use. Note that (unmodified) programs may be used to generate curves for commercial use. There are

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

See Also

• Elliptic Curve Cryptography
• Counting points on elliptic curves
• Hasse's theorem
• Chinese Remainder Theorem
• Division Polynomials
• Frobenius endomorphism

References

• A. Brown: Algorithms for Elliptic Curves over Finite Fields, EPFL - LMA. Avaliable at http://algo.epfl.ch/handouts/en/andrew.pdf
• A. Enge: Elliptic Curves and their Applications to Cryptography: An Introduction. Kluwer Academic Publishers, Dordrecht, 1999.
• N. Koblitz: A Course in Number Theory and Cryptography, Graduate Texts in Math. No. 114, Springer-Verlag, 1987. Second edition, 1994
• V. Müller : Die Berechnung der Punktanzahl von elliptischen kurven über endlichen Primkörpern. Master's Thesis. Universität des Saarlandes, Saarbrücken, 1991. Avaliable at http://lecturer.ukdw.ac.id/vmueller/publications.php
• G. Musiker: Schoof's Algorithm for Counting Points on $E(\mathbb {F} _{q})$. Avaliable at http://www-math.mit.edu/~musiker/schoof.pdf
• R. Schoof: Elliptic Curves over Finite Fields and the Computation of Square Roots mod p. Math. Comp., 44(170):483-494, 1985. Avaliable 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. Avaliable at http://www.mat.uniroma2.it/~schoof/ctg.pdf
• L. C. Washington: Elliptic Curves: Number Theory and Cryptography. Chapman & Hall/CRC, New York, 2003.