Fast algorithms for computing the eigenvalue in the Schoof-Elkies-Atkin algorithm

ABSTRACT

The Schoof-Elkies-Atkin algorithm is the best known algorithm for counting the number of points of an elliptic curve defined over a finite field of large characteristic. Several practical and asymptotical improvements for the phase called eigenvalue computation are proposed.

REFERENCES

• 1: A. O. L. Atkin. The number of points on an elliptic curve modulo a prime (II). Available on http://listserv.nodak.edu/archives/nmbrthry.html, 1992.
• 2: Ian F. Blake , G. Seroussi , N. P. Smart, Elliptic curves in cryptography, Cambridge University Press, New York, NY, 1999
• 3: A. Bostan, F. Morain, B. Salvy, and E. Schost. Fast algorithms for computing isogenies between elliptic curves. In preparation, Jan. 2006.
• 4: Eric Brier , Marc Joye, Weierstraß Elliptic Curves and Side-Channel Attacks, Proceedings of the 5th International Workshop on Practice and Theory in Public Key Cryptosystems: Public Key Cryptography, p.335-345, February 12-14, 2002
• 5: Jean Marc Couveignes , François Morain, Schoof's algorithm and isogeny cycles, Proceedings of the First International Symposium on Algorithmic Number Theory, p.43-58, May 06-09, 1994
• 6: L. Dewaghe, Remarks on the Schoof-Elkies-Atkin algorithm, Mathematics of Computation, v.67 n.223, p.1247-1252, July 1, 1998 [doi>10.1090/S0025-5718-98-00962-4]
• 7: N. D. Elkies. Elliptic and modular curves over finite fields and related computational issues. In D. A. Buell and J. T. Teitelbaum, editors, Computational Perspectives on Number Theory: Proceedings of a Conference in Honor of A. O. L. Atkin, volume 7 of AMS/IP Studies in Advanced Mathematics, pages 21--76. American Mathematical Society, International Press, 1998.
• 8: A. Enge. Computing modular polynomials in quasi-linear time. In preparation.
• 9: A. Enge, P. Gaudry, and F. Morain. Computing #E(GF(102004 + 4863)). http://listserv.nodak.edu/archives/nmbrthry.html, Dec. 2005.
• 10: Joachim von zur Gathen , Jürgen Gerhard, Modern computer algebra, Cambridge University Press, New York, NY, 1999
• 11: K. S. Kedlaya. Counting points on hyperelliptic curves using Monsky-Washnitzer cohomology. J. Ramanujan Math. Soc., 16(4):323--338, 2001.
• 12: S. Lang. Elliptic curves, diophantine analysis. Springer, 1978.
• 13: M. Maurer and V. Müller. Finding the eigenvalue in Elkies' algorithm. Experiment. Math., 10(2):275--285, 2001.
• 14: F. Morain. Calcul du nombre de points sur une courbe elliptique dans un corps fini : aspects algorithmiques. J. Théor. Nombres Bordeaux, 7:255--282, 1995.
• 15: T. Satoh. The canonical lift of an ordinary elliptic curve over a finite field and its point counting. J. Ramanujan Math. Soc., 15:247--270, 2000.
• 16: R. Schoof. Counting points on elliptic curves over finite fields. J. Thèor. Nombres Bordeaux, 7:219--254, 1995.
• 17: Victor Shoup, A new polynomial factorization algorithm and its implementation, Journal of Symbolic Computation, v.20 n.4, p.363-397, October 1995 [doi>10.1006/jsco.1995.1055]
• 18: Victor Shoup, Efficient computation of minimal polynomials in algebraic extensions of finite fields, Proceedings of the 1999 international symposium on Symbolic and algebraic computation, p.53-58, July 28-31, 1999, Vancouver, British Columbia, Canada [doi>10.1145/309831.309859]
• 19: F. Vercauteren. The SEA algorithm in characteristic 2. Preprint, 2000.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Number-theoretic computations (e.g., factoring, primality testing)

General Terms:
Algorithms

Keywords:
SEA algorithm, elliptic curves, point counting