Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Computing isogenies between elliptic curves
over $F_{p^n}$ using Couveignes's algorithm


Authors: R. Lercier and F. Morain
Journal: Math. Comp. 69 (2000), 351-370
MSC (1991): Primary 11G20; Secondary 11T71, 94A60, 11Y16
DOI: https://doi.org/10.1090/S0025-5718-99-01081-9
Published electronically: March 4, 1999
MathSciNet review: 1642770
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The heart of the improvements by Elkies to Schoof's algorithm for computing the cardinality of elliptic curves over a finite field is the ability to compute isogenies between curves. Elkies' approach is well suited for the case where the characteristic of the field is large. Couveignes showed how to compute isogenies in small characteristic. The aim of this paper is to describe the first successful implementation of Couveignes's algorithm. In particular, we describe the use of fast algorithms for performing incremental operations on series. We also insist on the particular case of the characteristic 2.


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

  • 1. A. O. L. Atkin, The number of points on an elliptic curve modulo a prime, Draft, 1988.
  • 2. -, The number of points on an elliptic curve modulo a prime (ii), Draft. Available on http://listserv.nodak.edu/archives/nmbrthry.html, 1992.
  • 3. A. O. L. Atkin and F. Morain, Elliptic curves and primality proving, Math. Comp. 61 203 (July 1993), 29-68. MR 93m:11136
  • 4. A. Borel, S. Chowla, C. S. Herz, K. Iwasawa, and J.-P. Serre, Seminar on complex multiplication, No. 21 in Lecture Notes in Math., Springer, 1966. MR 34:1278
  • 5. W. Bosma, Primality testing using elliptic curves, Tech. Rep. 85-12, Math. Institut, Universiteit van Amsterdam, 1985.
  • 6. R. P. Brent, F. G. Gustavson, and D. Y. Y. Yun, Fast solution of Toeplitz systems of equations and computation of Padé approximants, J. Algorithms 1 (1980), 259-295. MR 82d:65033
  • 7. R. P. Brent and H. T. Kung, Fast algorithms for manipulating formal power series, J. Assoc. Comput. Mach. 25 (1978), 581-595. MR 58:25090
  • 8. L. Comtet, Calcul pratique des coefficients de Taylor d'une fonction algébrique, Enseignement Math. 10 (1964), 267-270. MR 29:1738
  • 9. J.-M. Couveignes, Quelques calculs en théorie des nombres, Thèse, Université de Bordeaux I, July 1994.
  • 10. -, Computing $l$-isogenies using the $p$-torsion, In Algorithmic Number Theory (1996), H. Cohen, Ed., vol. 1122 of Lecture Notes in Comput. Sci., Springer-Verlag, pp. 59-65. Second International Symposium, ANTS-II, Talence, France, May 1996, Proceedings. MR 98j:11046
  • 11. -, Isomorphisms between Artin-Schreier towers. Draft, available on http://www.math.u-bordeaux.fr/$^\sim$couveign, Jan. 1997.
  • 12. J.-M. Couveignes, L. Dewaghe, and F. Morain, Isogeny cycles and the Schoof-Elkies-Atkin algorithm, Research Report LIX/RR/96/03, LIX, Apr. 1996.
  • 13. J.-M. Couveignes and F. Morain, Schoof's algorithm and isogeny cycles. In ANTS-I (1994), L. Adleman and M.-D. Huang, Eds., vol. 877 of Lecture Notes in Comput. Sci., Springer-Verlag, pp. 43-58. 1st Algorithmic Number Theory Symposium-Cornell University, May 6-9, 1994. MR 95m:11147
  • 14. M. Deuring, Die Typen der Multiplikatorenringe elliptischer Funktionenkörper, Abh. Math. Sem. Hamburg 14 (1941), 197-272. MR 3:104f
  • 15. L. Dewaghe, Un corollaire aux formules de Vélu, Preprint, Dec. 1995.
  • 16. N. D. Elkies, Explicit isogenies, Draft, 1991.
  • 17. -, Elliptic and modular curves over finite fields and related computational issues, In Computational Perspectives on Number Theory: Proceedings of a Conference in Honor of A. O. L. Atkin (1998), D. A. Buell and J. T. Teitelbaum, Eds., vol. 7 of AMS/IP Studies in Advanced Mathematics, American Mathematical Society, International Press. CMP 98:05
  • 18. R. Fricke, Die elliptischen Funktionen und ihre Anwendungen, Teubner, Leipzig, 1992.
  • 19. A. Fröhlich, Formal groups, vol. 74 of Lecture Notes in Math., Springer-Verlag, 1968. MR 39:4164
  • 20. S. Goldwasser and J. Kilian, Almost all primes can be quickly certified, In Proc. 18th STOC (1986), ACM, pp. 316-329. May 28-30, Berkeley.
  • 21. H. Gunji, The Hasse invariant and $p$-division points of an elliptic curve, Arch. Math. 27 2 (1976), 148-158. MR 54:325
  • 22. G. Harper, A. Menezes, and S. Vanstone, Public-key cryptosystems with very small key length, In Advances in Cryptoloy - EUROCRYPT '92 (1993), R. A. Rueppel, Ed., vol. 658 of Lecture Notes in Comput. Sci., Springer-Verlag, pp. 163-173. Workshop on the Theory and Application of Cryptographic Techniques, Balatonfüred, Hungary, May 24-28, 1992, Proceedings.
  • 23. D. Husemöller, Elliptic curves, vol. 111 of Graduate Texts in Mathematics, Springer, 1987. MR 88h:11039
  • 24. M. Kaneko and D. Zagier, Supersingular $j$-invariants, hypergeometric series, and Atkin's orthogonal polynomials. In Computational Perspectives on Number Theory: Proceedings of a Conference in Honor of A. O. L. Atkin (1998), D. A. Buell and J. T. Teitelbaum, Eds., vol. 7 of AMS/IP Studies in Advanced Mathematics, American Mathematical Society, International Press. CMP 98:05
  • 25. N. Koblitz, Elliptic curve cryptosystems, Math. Comp. 48 177 (Jan. 1987), 203-209. MR 88b:94017
  • 26. F. Lehmann, M. Maurer, V. Müller, and V. Shoup, Counting the number of points on elliptic curves over finite fields of characteristic greater than three. In ANTS-I (1994), L. Adleman and M.-D. Huang, Eds., vol. 877 of Lecture Notes in Comput. Sci., Springer-Verlag, pp. 60-70. 1st Algorithmic Number Theory Symposium-Cornell University, May 6-9, 1994. MR 95m:11148
  • 27. H. W. Lenstra, Jr., Factoring integers with elliptic curves, Ann. of Math. (2) 126 (1987), 649-673. MR 89g:11125
  • 28. R. Lercier, Computing isogenies in $F_{2^n}$, In Algorithmic Number Theory (1996), H. Cohen, Ed., vol. 1122 of Lecture Notes in Comput. Sci., Springer-Verlag, pp. 197-212. Second International Symposium, ANTS-II, Talence, France, May 1996, Proceedings. MR 98d:11069
  • 29. -, Algorithmique des courbes elliptiques dans les corps finis, Thèse, École polytecnique, June 1997.
  • 30. R. Lercier and F. Morain, Counting points on elliptic curves over $F_{p^n}$ using Couveignes's algorithm, Research Report LIX/RR/95/09, École Polytechnique-LIX, Sept. 1995. MR 96h:11060
  • 31. -, Counting the number of points on elliptic curves over finite fields: strategies and performances, In Advances in Cryptology - EUROCRYPT '95 (1995), L. C. Guillou and J.-J. Quisquater, Eds., vol. 921 of Lecture Notes in Comput. Sci., pp. 79-94. International Conference on the Theory and Application of Cryptographic Techniques, Saint-Malo, France, May 1995, Proceedings. MR 96h:11060
  • 32. -, Algorithms for computing isogenies between elliptic curves, In Computational Perspectives on Number Theory: Proceedings of a Conference in Honor of A. O. L. Atkin (1998), D. A. Buell and J. T. Teitelbaum, Eds., vol. 7 of AMS/IP Studies in Advanced Mathematics, American Mathematical Society, International Press. CMP 98:05
  • 33. J. L. Massey, Shift-register and BCH decoding, IEEE Trans. Inform. Theory IT-15, 1 (Jan. 1969), 122-127. MR 39:3887
  • 34. R. McEliece, Finite fields for computer scientists and engineers, Kluwer International Series in Engineering and Computer Science. Kluwer Academic Publishers, 1988. MR 88h:11091
  • 35. A. Menezes and S. Vanstone, Isomorphism classes of elliptic curves over finite fields of characteristic 2, Utilitas Math. 38 (1990), 135-153. MR 92a:11071
  • 36. A. J. Menezes, Elliptic curve public key cryptosystems, Kluwer Academic Publishers, 1993.
  • 37. A. J. Menezes, S. A. Vanstone, and R. J. Zuccherato, Counting points on elliptic curves over $F_{2^m}$, Math. Comp. 60, 201 (Jan. 1993), 407-420. MR 93f:11098
  • 38. V. Miller, Use of elliptic curves in cryptography, In Advances in Cryptology - CRYPTO '86 (1987), A. M. Odlyzko, Ed., vol. 263 of Lecture Notes in Comput. Sci., Springer-Verlag, pp. 417-426. Proceedings, Santa Barbara (USA), August 11-15, 1986. MR 88b:68040
  • 39. P. L. Montgomery, Speeding the Pollard and elliptic curve methods of factorization, Math. Comp. 48, 177 (Jan. 1987), 243-264. MR 88e:11130
  • 40. F. Morain, Calcul du nombre de points sur une courbe elliptique dans un corps fini: aspects algorithmiques, J. Théor. Nombres Bordeaux 7 (1995), 255-282. MR 97i:11111
  • 41. -, Classes d'isomorphismes des courbes elliptiques supersingulières en caractéristique $\ge 3$, Utilitas Math. 52 (1997), 241-253. CMP 98:08
  • 42. V. Müller, Ein Algorithmus zur Bestimmung der Punktanzahl elliptischer Kurven über endlichen Körpern der Charakteristik größer drei, Ph.D. thesis, Technischen Fakultät der Universität des Saarlandes, 1995.
  • 43. B. Salvy, P. Zimmermann, and P. Gfun, A maple package for the manipulation of generating and holonomic functions in one variable, ACM Transactions on Mathematical Software 20, 2 (1994), 163-177.
  • 44. R. Schoof, Counting points on elliptic curves over finite fields, J. Théor. Nombes Bordeaux 7 (1995), 219-254. MR 97i:11070
  • 45. J. H. Silverman, The arithmetic of elliptic curves, vol. 106 of Graduate Texts in Mathematics, Springer, 1986. MR 87g:11061
  • 46. J. Tate, Endomorphisms of Abelian varieties over finite fields, Invent. Math. 2 (1966), 134-144. MR 34:5829

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (1991): 11G20, 11T71, 94A60, 11Y16

Retrieve articles in all journals with MSC (1991): 11G20, 11T71, 94A60, 11Y16


Additional Information

R. Lercier
Affiliation: CELAR/SSIG, Route de Laillé, F-35170 Bruz, France
Email: lercier@celar.fr

F. Morain
Affiliation: Laboratoire d’Informatique de l’École polytechnique (LIX - UMR 7650), F-91128 Palaiseau Cedex, France
Email: morain@lix.polytechnique.fr

DOI: https://doi.org/10.1090/S0025-5718-99-01081-9
Keywords: Elliptic curves, finite fields, isogenies, formal groups, Schoof's algorithm
Received by editor(s): May 6, 1996
Received by editor(s) in revised form: March 10, 1998
Published electronically: March 4, 1999
Additional Notes: The second author is on leave from the French Department of Defense, Délégation Générale pour l’Armement
Article copyright: © Copyright 1999 American Mathematical Society

American Mathematical Society