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. 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 for the group, of elliptic curves over a finite field, where q = pk 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 and Atkin.
Several algorithms make use of the fact that groups of the form are subject to an important theorem due to Hasse, that bounds the number of points to be considered. Hasse's theorem states that if E is an elliptic curve over the finite field, then the cardinality of satisfies

Naive approach

The naive approach to counting points, which is the least sophisticated, involves running through all the elements of the field and testing which ones satisfy the Weierstrass form of the elliptic curve

Example

Let E be the curve y2 = x3 + x + 1 over. To count points on E, we make a
list of the possible values of x, then of the quadratic residues of x mod 5, then of x3 + x + 1 mod 5, then of y of x3 + x + 1 mod 5. This yields the points on E.
Points

E.g. the last row is computed as follows: If you insert in the equation you get as result. This result can be achieved if . So the points for the last row are.
Therefore, has cardinality of 9: the 8 points listed before and the point at infinity.
This algorithm requires running time O, because all the values of must be considered.

Baby-step giant-step

An improvement in running time is obtained using a different approach: we pick an element by selecting random values of until is a square in and then computing the square root of this value in order to get.
Hasse's theorem tells us that lies in the interval. Thus, by Lagrange's theorem, finding a unique lying in this interval and satisfying, results in finding the cardinality of. The algorithm fails if there exist two integers and in the interval such that. In such a case it usually suffices to repeat the algorithm with another randomly chosen point in.
Trying all values of in order to find the one that satisfies takes around steps.
However, by applying the baby-step giant-step algorithm to, we are able to speed this up to around steps. The algorithm is as follows.

The algorithm

1. choose integer,
2. FOR DO
3.
4. ENDFOR
5.
6.
7. REPEAT compute the points
8. UNTIL : \\the -coordinates are compared
9. \\note
10. Factor. Let be the distinct prime factors of.
11. WHILE DO
12. IF
13. THEN
14. ELSE
15. ENDIF
16. ENDWHILE
17. \\note is the order of the point
18. WHILE divides more than one integer in
19. DO choose a new point and go to 1.
20. ENDWHILE
21. RETURN \\it is the cardinality of

Schoof's algorithm

A theoretical breakthrough for the problem of computing the cardinality of groups of the type 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. It suffices to compute modulo an integer. This is achieved by computing modulo primes whose product exceeds, and then applying the Chinese remainder theorem. The key to the algorithm is using the division polynomial to efficiently compute modulo.
The running time of Schoof's Algorithm is polynomial in, with an asymptotic complexity of, where denotes the complexity of integer multiplication. Its space complexity is.

Schoof–Elkies–Atkin algorithm

In the 1990s, Noam Elkies, followed by A. O. L. Atkin devised improvements to Schoof's basic algorithm by making a distinction among the primes that are used. A prime is called an Elkies prime if the characteristic equation of the Frobenius endomorphism,, splits over. Otherwise is called an Atkin prime. Elkies primes are the key to improving the asymptotic complexity of Schoof's algorithm. Information obtained from the Atkin primes permits a further improvement which is asymptotically negligible but can be quite important in practice. The modification of Schoof's algorithm to use Elkies and Atkin primes is known as the Schoof–Elkies–Atkin algorithm.
The status of a particular prime depends on the elliptic curve, and can be determined using the modular polynomial. If the univariate polynomial has a root in, where denotes the j-invariant of, then is an Elkies prime, and otherwise it is an Atkin prime. In the Elkies case, further computations involving modular polynomials are used to obtain a proper factor of the division polynomial. The degree of this factor is, whereas has degree.
Unlike Schoof's algorithm, the SEA algorithm is typically implemented as a probabilistic algorithm, so that root-finding and other operations can be performed more efficiently. Its computational complexity is dominated by the cost of computing the modular polynomials, but as these do not depend on, they may be computed once and reused. Under the heuristic assumption that there are sufficiently many small Elkies primes, and excluding the cost of computing modular polynomials, the asymptotic running time of the SEA algorithm is, where. Its space complexity is, but when precomputed modular polynomials are used this increases to.