Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

 

``Chinese & Match'', an alternative to Atkin's ``Match and Sort'' method used in the SEA algorithm


Authors: Antoine Joux and Reynald Lercier
Journal: Math. Comp. 70 (2001), 827-836
MSC (2000): Primary 11Y16; Secondary 68Q25
Published electronically: March 2, 2000
MathSciNet review: 1680891
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: A classical way to compute the number of points of elliptic curves defined over finite fields from partial data obtained in SEA (Schoof Elkies Atkin) algorithm is a so-called ``Match and Sort'' method due to Atkin. This method is a ``baby step/giant step'' way to find the number of points among $C$candidates with $O(\sqrt{C})$ elliptic curve additions. Observing that the partial information modulo Atkin's primes is redundant, we propose to take advantage of this redundancy to eliminate the usual elliptic curve algebra in this phase of the SEA computation. This yields an algorithm of similar complexity, but the space needed is smaller than what Atkin's method requires. In practice, our technique amounts to an acceleration of Atkin's method, allowing us to count the number of points of an elliptic curve defined over $\mathbb{F} _{2^{1663}}$. As far as we know, this is the largest point-counting computation to date. Furthermore, the algorithm is easily parallelized.


References [Enhancements On Off] (What's this?)

  • [Atk88] A. O. L. Atkin.
    The number of points on an elliptic curve modulo a prime, 1988.
    Email on the Number Theory Mailing List.
  • [Atk91] A. O. L. Atkin.
    The number of points on an elliptic curve modulo a prime, 1991.
    Email on the Number Theory Mailing List.
  • [CDM96] J.-M. Couveignes, L. Dewaghe, and F. Morain.
    Isogeny cycles and the Schoof-Elkies-Atkin algorithm.
    Research Report LIX/RR/96/03, LIX, April 1996.
  • [CM94] Jean-Marc Couveignes and François Morain, Schoof’s algorithm and isogeny cycles, Algorithmic number theory (Ithaca, NY, 1994) Lecture Notes in Comput. Sci., vol. 877, Springer, Berlin, 1994, pp. 43–58. MR 1322711 (95m:11147), http://dx.doi.org/10.1007/3-540-58691-1_42
  • [Cou94] J. M. Couveignes.
    Quelques calculs en théorie des nombres.
    thèse, Université de Bordeaux I, July 1994.
  • [Elk91] N. D. Elkies.
    Explicit isogenies.
    Draft, 1991.
  • [Elk97] Noam D. Elkies, Elliptic and modular curves over finite fields and related computational issues, Computational perspectives on number theory (Chicago, IL, 1995) AMS/IP Stud. Adv. Math., vol. 7, Amer. Math. Soc., Providence, RI, 1998, pp. 21–76. MR 1486831 (99a:11078)
  • [JL98] A. Joux and R. Lercier.
    Cardinality of an elliptic curve defined over GF($2^{1663}$), 1998.
    Email on the Number Theory Mailing List.
  • [Ler97] R. Lercier.
    Algorithmique des courbes elliptiques dans les corps finis.
    thèse, École polytechnique, June 1997.
  • [LM97] R. Lercier and F. Morain, Algorithms for computing isogenies between elliptic curves, Computational perspectives on number theory (Chicago, IL, 1995) AMS/IP Stud. Adv. Math., vol. 7, Amer. Math. Soc., Providence, RI, 1998, pp. 77–96. MR 1486832 (99a:11079)
  • [Mor95] François Morain, Calcul du nombre de points sur une courbe elliptique dans un corps fini: aspects algorithmiques, J. Théor. Nombres Bordeaux 7 (1995), no. 1, 255–282 (French, with English and French summaries). Les Dix-huitièmes Journées Arithmétiques (Bordeaux, 1993). MR 1413579 (97i:11069)
  • [Mül95] V. Müller.
    Ein Algorithmus zur bestimmung der Punktanzahl elliptisher kurven über endlichen körpen der charakteristik größer drei.
    PhD thesis, Technischen Fakultät der Universität des Saarlandes, February 1995.
  • [Sch85] René Schoof, Elliptic curves over finite fields and the computation of square roots mod 𝑝, Math. Comp. 44 (1985), no. 170, 483–494. MR 777280 (86e:11122), http://dx.doi.org/10.1090/S0025-5718-1985-0777280-6
  • [Sch95] René Schoof, Counting points on elliptic curves over finite fields, J. Théor. Nombres Bordeaux 7 (1995), no. 1, 219–254. Les Dix-huitièmes Journées Arithmétiques (Bordeaux, 1993). MR 1413578 (97i:11070)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11Y16, 68Q25

Retrieve articles in all journals with MSC (2000): 11Y16, 68Q25


Additional Information

Antoine Joux
Affiliation: SCSSI, 18 rue du Dr. Zamenhoff, F-92131 Issy-les-Moulineaux, France
Email: Antoine.Joux@ens.fr

Reynald Lercier
Affiliation: CELAR, Route de Laillé, F-35998 Rennes Armées, France
Email: lercier@celar.fr

DOI: http://dx.doi.org/10.1090/S0025-5718-00-01200-X
PII: S 0025-5718(00)01200-X
Received by editor(s): January 22, 1999
Received by editor(s) in revised form: April 20, 1999
Published electronically: March 2, 2000
Article copyright: © Copyright 2000 American Mathematical Society