Counting points on elliptic curves

An important aspect in the study of elliptic curves is devising effective ways of counting points on the curve. There have been several approaches to do so, and the algorithms devised have proved to be useful tools in the study of various fields such as number theory, and more recently in cryptography and Digital Signature Authentication (See elliptic curve cryptography and elliptic curve DSA). While in number theory they have important consequences in the solving of Diophantine equations, with respect to cryptography, they enable us to make effective use of the difficulty of the discrete logarithm problem (DLP) for the group $E(\mathbb {F} _{q})$, of elliptic curves over a finite field $\mathbb {F} _{q}$, where q = p^k and p is a prime. The DLP, as it has come to be known, is a widely used approach to Public key cryptography, and the difficulty in solving this problem determines the level of security of the cryptosystem. This article covers algorithms to count points on elliptic curves over fields of large characteristic, in particular p > 3. For curves over fields of small characteristic more efficient algorithms based on p-adic methods exist.

Approaches to counting points on elliptic curves

There are several approaches to the problem. Beginning with the naive approach, we trace the developments up to Schoof's definitive work on the subject, while also listing the improvements to Schoof's algorithm made by Elkies (1990) and Atkin (1992).

Several algorithms make use of the fact that groups of the form $E(\mathbb {F} _{q})$ are subject to an important theorem due to Hasse, that bounds the number of points to be considered.

Hasse's theorem Let E be an elliptic curve over the finite field $\mathbb {F} _{q}$. Then the order of $E(\mathbb {F} _{q})$ satisfies

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

Naive approach

The naive approach to counting points, which is the least sophisticated, involves running through all the elements of the field $\mathbb {F} _{q}$ and testing which ones satisfy the Weierstrass form of the elliptic curve

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

Example

Let $E$ be the curve $y^{2}=x^{3}+x+1$ over $\mathbb {F} _{5}$. To count points on $E$, we make a list of the possible values of $x$, then of $x^{3}+x+1{\pmod {5}}$, then of the square roots $y$ of $x^{3}+x+1{\pmod {5}}$. This yields the points on $E$.

$x$	$x^{3}+x+1$	$y$	Points
$\quad 0$	$1$	$\pm 1$	$(0,1),(0,4)$
$\quad 1$	$3$	$-$	$-$
$\quad 2$	$1$	$\pm 1$	$(2,1),(2,4)$
$\quad 3$	$1$	$\pm 1$	$(3,1),(3,4)$
$\quad 4$	$4$	$\pm 2$	$(4,2),(4,3)$

Therefore, $E(\mathbb {F} _{5})$ has order 9: the 8 points listed before and the point at infinity.

This algorithm requires running time $O(q)$, because all the values of $x\in \mathbb {F} _{q}$ must be considered.

Baby-step giant-step

An improvement in running time is obtained using a different approach: we pick an element $P=(x,y)\in E(\mathbb {F} _{q})$ by selecting random values of $x$ until $x^{3}+Ax+B$ is a square in $\mathbb {F} _{q}$ and then computing the square root of this value in order to get $y$. Hasse's theorem tells us that $|E(\mathbb {F} _{q})|$ lies in the interval $(q+1-2{\sqrt {q}},q+1+2{\sqrt {q}})$. Thus, by Lagrange's theorem, finding a unique $M$ lying in this interval and satisfying $MP=O$, results in finding the cardinality of $E(\mathbb {F} _{q})$. The algorithm fails if there exist two integers $M$ and $M'$ in the interval such that $MP=M'P=O$. In such a case it usually suffices to repeat the algorithm with another randomly chosen point in $E(\mathbb {F} _{q})$.

Trying all values of $M$ in order to find the one that satisfies $MP=O$ takes around $4{\sqrt {q}}$ steps.

However, by applying the baby-step giant-step algorithm to $E(\mathbb {F} _{q})$, we are able to speed this up to around $4{\sqrt[{4}]{q}}$ steps. The algorithm is as follows.

The algorithm

1. choose $m$ integer, $m>{\sqrt[{4}]{q}}$
2. FOR{$j=0$ to $m$} DO 
3.    $P_{j}\leftarrow jP$
4. ENDFOR
5. $L\leftarrow 1$
6. $Q\leftarrow (q+1)P$
7. REPEAT compute the points $Q+k(2mP)$
8. UNTIL $\exists j$: $Q+k(2mP)=\pm P_{j}$  \\the $x$-coordinates are compared
9. $M\leftarrow q+1+2mk\mp j$     \\note $MP=O$
10. Factor $M$. Let $p_{1},\ldots ,p_{r}$ be the distinct prime factors of $M$.
11. WHILE $i\leq r$ DO
12.    IF ${\frac {M}{p_{i}}}P=O$
13.       THEN $M\leftarrow {\frac {M}{p_{i}}}$
14.       ELSE $i\leftarrow i+1$ 
15.    ENDIF
16. ENDWHILE
17. $L\leftarrow \operatorname {lcm} (L,M)$     \\note $M$ is the order of the point $P$
18. WHILE $L$ divides more than one integer $N$ in $(q+1-2{\sqrt {q}},q+1+2{\sqrt {q}})$
19.    DO choose a new point $P$ and go to 1.
20. ENDWHILE
21. RETURN $N$     \\it is the cardinality of $E(\mathbb {F} _{q})$

Notes to the algorithm

• In line 8. we assume the existence of a match. Indeed, the following lemma assures that such a match exists.

Let $a$ be an integer with $|a|\leq 2m^{2}$. There exist integers $a_{0}$ and $a_{1}$ with
$-m<a_{0}\leq m{\mbox{ and }}-m\leq a_{1}\leq m{\mbox{ s.t. }}a=a_{0}+2ma_{1}.$
     

• Computing $(j+1)P$ once $jP$ has been computed can be done by adding $P$ to $jP$ instead of computing the complete scalar multiplication anew. The complete computation thus requires $m$ additions. $2mP$ can be obtained with one doubling from $mP$. The computation of $Q$ requires $\log(q+1)$ doublings and $w$ additions, where $w$ is the number of nonzero digits in the binary representation of $q+1$; note that knowledge of the $jP$ and $2mP$ allows us to reduce the number of doublings. Finally, to get from $Q+k(2mP)$ to $Q+(k+1)(2mP)$, simply add $2mP$ rather than recomputing everything.

• We are assuming that we can factor $M$. If not, we can at least find all the small prime factors $p_{i}$ and check that ${\frac {M}{p_{i}}}\neq O$ for these. Then $M$ will be a good candidate for the order of $P$.

• The conclusion of step 17 can be proved using elementary group theory: since $MP=O$, the order of $P$ divides $M$. If no proper divisor ${\bar {M}}$ of $M$ realizes ${\bar {M}}P=O$, then $M$ is the order of $P$.

One drawback of this method is that there is a need for too much memory when the group becomes large. In order to address this, it might be more efficient to store only the $x$ coordinates of the points $jP$ (along with the corresponding integer $j$). However, this leads to an extra scalar multiplication in order to choose between $-j$ and $+j$.

One must note that other generic algorithms for computing discrete logarithms exist, such as the Pollard's rho algorithm for logarithms and the Pollard kangaroo methods, which do not use memory. Pollard kangaroo allows to search for a solution in prescribed subsets and its running time is $O({\sqrt[{4}]{q}})$.

Schoof's algorithm

Main article: Schoof's algorithm

A theoretical breakthrough for the problem of computing the cardinality of groups of the type $E(\mathbb {F} _{q})$ was achieved by René Schoof, who, in 1985, published the first deterministic polynomial time algorithm. Central to Schoof's algorithm are the use of division polynomials and Hasse's theorem, along with the Chinese remainder theorem.

Schoof's insight exploits the fact that, by Hasse's Theorem, there is a finite range of possible values for $|E(\mathbb {F} _{q})|$. It suffices to compute $|E(\mathbb {F} _{q})|$ modulo an integer $N>4{\sqrt {q}}$. This is achieved by computing $|E(\mathbb {F} _{q}|$ modulo primes $\ell _{1},\ldots ,\ell _{s}$ whose product exceeds $4{\sqrt {q}}$, and then applying the Chinese remainder theorem. The key to the algorithm is using the division polynomial $\psi _{\ell }$ to efficiently compute $|E(\mathbb {F} _{q})|$ modulo $\ell$.

The running time of Schoof's Algorithm is polynomial in $n=\log {q}$, with an asymptotic complexity of $O(n^{2}M(n^{3})/\log {n})=O(n^{5+o(1)})$, where $M(n)$ denotes the complexity of multiplication.

Schoof–Elkies–Atkin algorithm

Main article: Schoof–Elkies–Atkin algorithm

In the 1990s, Noam Elkies, followed by A. O. L. 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)$.

See also

• Schoof's algorithm
• Elliptic curve cryptography
• Baby-step giant-step
• Public key cryptography
• Schoof-Elkies-Atkin algorithm
• Pollard rho
• Pollard kangaroo
• Elliptic curve primality proving

Bibliography

• A. Enge: Elliptic Curves and their Applications to Cryptography: An Introduction. Kluwer Academic Publishers, Dordrecht, 1999.
• G. Musiker: Schoof's Algorithm for Counting Points on $E(\mathbb {F} _{q})$. Available at http://www.math.mit.edu/~musiker/schoof.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
• L. C. Washington: Elliptic Curves: Number Theory and Cryptography. Chapman \& Hall/CRC, New York, 2003.
• C. Peters: Counting points on elliptic curves over $\mathbb {F} _{q}$. Available at http://www.win.tue.nl/~cpeters/presentations/2008.eccs.pdf