 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 , of elliptic curves over a finite field , 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 padic methods exist.
Contents
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 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 . Then the order 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 y^{2} = x^{3} + x + 1 over . To count points on E, we make a list of the possible values of x, then of x^{3} + x + 1(mod 5), then of the square roots y of x^{3} + x + 1(mod 5). This yields the points on E.
x x^{3} + x + 1 y Points 1 (0,1),(0,4) 3 − − 1 (2,1),(2,4) 1 (3,1),(3,4) 4 (4,2),(4,3) Therefore, 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 must be considered.
Babystep giantstep
An improvement in running time is obtained using a different approach: we pick an element by selecting random values of x until x^{3} + Ax + B is a square in and then computing the square root of this value in order to get y. Hasse's theorem tells us that lies in the interval . Thus, by Lagrange's theorem, finding a unique M lying in this interval and satisfying MP = O, results in finding the cardinality of . 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 .
Trying all values of M in order to find the one that satisfies MP = O takes around steps.
However, by applying the babystep giantstep algorithm to , we are able to speed this up to around steps. The algorithm is as follows.
The algorithm
1. choose m integer, 2. FOR{j = 0 to m} DO 3. 4. ENDFOR 5. 6. 7. REPEAT compute the points Q + k(2mP) 8. UNTIL : \\the xcoordinates are compared 9. \\note MP = O 10. Factor M. Let be the distinct prime factors of M. 11. WHILE DO 12. IF 13. THEN 14. ELSE 15. ENDIF 16. ENDWHILE 17. \\note M is the order of the point P 18. WHILE L divides more than one integer N in 19. DO choose a new point P and go to 1. 20. ENDWHILE 21. RETURN N \\it is the cardinality of
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 . There exist integers a_{0} and a_{1} with
 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 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 of M realizes , 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.
There are other generic algorithms for computing the order of a group element that are more space efficient, such as Pollard's rho algorithm and the Pollard kangaroo method. The Pollard kangaroo method allows one to search for a solution in a prescribed interval, yielding a running time of , using O(log ^{2}q) space.
Schoof's algorithm
Main article: Schoof's algorithmA 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 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. Its space complexity is O(n^{3}).
Schoof–Elkies–Atkin algorithm
Main article: Schoof–Elkies–Atkin algorithmIn 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, ϕ^{2} − tϕ + q = 0, 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 (SEA) 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 j(E) denotes the jinvariant of E, 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 (of the Las Vegas type), so that rootfinding 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 E, 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 O(n^{2}M(n^{2}) / log n) = O(n^{4 + o(1)}), where n = log q. Its space complexity is O(n^{3}log n), but when precomputed modular polynomials are used this increases to O(n^{4}).
See also
 Schoof's algorithm
 Elliptic curve cryptography
 Babystep giantstep
 Public key cryptography
 Schoof–Elkies–Atkin algorithm
 Pollard rho
 Pollard kangaroo
 Elliptic curve primality proving
Bibliography
 I. Blake, G. Seroussi, and N. Smart: Elliptic Curves in Cryptography, Cambridge University Press, 1999.
 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 . 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:219254, 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 . Available at http://www.win.tue.nl/~cpeters/presentations/2008.eccs.pdf
References
Categories: Elliptic curves
Wikimedia Foundation. 2010.
Look at other dictionaries:
Elliptic curve cryptography — (ECC) is an approach to public key cryptography based on the algebraic structure of elliptic curves over finite fields. The use of elliptic curves in cryptography was suggested independently by Neal Koblitz[1] and Victor S. Miller[2] in 1985.… … Wikipedia
Moduli of algebraic curves — In algebraic geometry, a moduli space of (algebraic) curves is a geometric space (typically a scheme or an algebraic stack) whose points represent isomorphism classes of algebraic curves. It is thus a special case of a moduli space. Depending on… … Wikipedia
Division polynomials — In mathematics the division polynomials provide a way to calculate multiples of points on elliptic curves over Finite fields. They play a central role in the study of counting points on elliptic curves in Schoof s algorithm. Contents 1 Definition … Wikipedia
Riemann surface — For the Riemann surface of a subring of a field, see Zariski–Riemann space. Riemann surface for the function ƒ(z) = √z. The two horizontal axes represent the real and imaginary parts of z, while the vertical axis represents the real… … Wikipedia
Plane curve — In mathematics, a plane curve is a curve in a Euclidean plane (cf. space curve). The most frequently studied cases are smooth plane curves (including piecewise smooth plane curves), and algebraic plane curves. A smooth plane curve is a curve in a … Wikipedia
De Franchis theorem — In mathematics, the de Franchis theorem is one of a number of closely related statements applying to compact Riemann surfaces, or, more generally, algebraic curves, X and Y, in the case of genus g > 1. The simplest is that the automorphism… … Wikipedia
Genus–degree formula — In classical algebraic geometry, the genus–degree formula relates the degree d of a non singular plane curve with its arithmetic genus g via the formula: A singularity of order r decreases the genus by .[1] Proofs The proof follows immediately… … Wikipedia
René Schoof — ist ein niederländischer Mathematiker, der sich mit algebraischer Zahlentheorie, arithmetischer algebraischer Geometrie, algorithmischer Zahlentheorie und Kodierungstheorie beschäftigt. René Schoof, Oberwolfach 2009 Schoof promovierte 1985 an der … Deutsch Wikipedia
Néron–Tate height — In number theory, the Néron–Tate height (or canonical height) is a quadratic form on the Mordell Weil group of rational points of an abelian variety defined over a global field. It is named after André Néron and John Tate. Contents 1 Definition… … Wikipedia
mathematics — /math euh mat iks/, n. 1. (used with a sing. v.) the systematic treatment of magnitude, relationships between figures and forms, and relations between quantities expressed symbolically. 2. (used with a sing. or pl. v.) mathematical procedures,… … Universalium