Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

Fast algorithms for computing isogenies between elliptic curves


Authors: A. Bostan, F. Morain, B. Salvy and É. Schost
Journal: Math. Comp. 77 (2008), 1755-1778
MSC (2000): Primary 11Y16, 94A60; Secondary 11G20
DOI: https://doi.org/10.1090/S0025-5718-08-02066-8
Published electronically: January 18, 2008
MathSciNet review: 2398793
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We survey algorithms for computing isogenies between elliptic curves defined over a field of characteristic either 0 or a large prime. We introduce a new algorithm that computes an isogeny of degree $ \ell$ ($ \ell$ different from the characteristic) in time quasi-linear with respect to $ \ell$. This is based in particular on fast algorithms for power series expansion of the Weierstrass $ \wp$-function and related functions.


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

  • 1. C. Alonso, J. Gutierrez, and T. Recio.
    A rational function decomposition algorithm by near-separated polynomials.
    Journal of Symbolic Computation, 19(6):527-544, 1995. MR 1370620 (96j:13025)
  • 2. A. O. L. Atkin.
    The number of points on an elliptic curve modulo a prime (II).
    Manuscript. Available at http://listserv.nodak.edu/archives/nmbrthry.html, July 1992.
  • 3. D. J. Bernstein.
    Composing power series over a finite ring in essentially linear time.
    Journal of Symbolic Computation, 26(3):339-341, 1998. MR 1633872
  • 4. D. J. Bernstein.
    Removing redundancy in high-precision Newton iteration, 2000.
    Available on-line at http://cr.yp.to/fastnewton.html.
  • 5. I. Blake, G. Seroussi, and N. Smart.
    Elliptic curves in cryptography, volume 265 of London Mathematical Society Lecture Notes Series.
    Cambridge University Press, 1999. MR 1771549 (2001i:94048)
  • 6. R. P. Brent.
    Multiple-precision zero-finding methods and the complexity of elementary function evaluation.
    In Analytic computational complexity, pages 151-176. Academic Press, New York, 1976.
    Proceedings of a Symposium held at Carnegie-Mellon University, Pittsburgh, PA, 1975. MR 0423869 (54:11843)
  • 7. R. P. Brent, F. G. Gustavson, and D. Y. Y. Yun.
    Fast solution of Toeplitz systems of equations and computation of Padé approximants.
    Journal of Algorithms, 1(3):259-295, 1980. MR 604867 (82d:65033)
  • 8. R. P. Brent and H. T. Kung.
    Fast algorithms for manipulating formal power series.
    Journal of the ACM, 25(4):581-595, 1978. MR 0520733 (58:25090)
  • 9. E. Brier and M. Joye.
    Fast point multiplication on elliptic curves through isogenies.
    In Applied algebra, algebraic algorithms and error-correcting codes (Toulouse, 2003), volume 2643 of Lecture Notes in Computer Science, pages 43-50. Springer, Berlin, 2003. MR 2042411 (2005a:14029)
  • 10. D. G. Cantor and E. Kaltofen.
    On fast multiplication of polynomials over arbitrary algebras.
    Acta Informatica, 28(7):693-701, 1991. MR 1129288 (92i:68068)
  • 11. L. S. Charlap, R. Coley, and D. P. Robbins.
    Enumeration of rational points on elliptic curves over finite fields.
    Manuscript, 1991.
  • 12. S. Cook.
    On the minimum computation time of functions.
    Ph.D. thesis, Harvard University, 1966.
  • 13. J.-M. Couveignes.
    Quelques calculs en théorie des nombres.
    Thèse, Université de Bordeaux I, July 1994.
  • 14. J.-M. Couveignes.
    Computing $ l$-isogenies using the $ p$-torsion.
    In H. Cohen, editor, Algorithmic Number Theory, volume 1122 of Lecture Notes in Computer Science, pages 59-65. Springer-Verlag, 1996.
    Proceedings of the Second International Symposium, ANTS-II, Talence, France, May 1996. MR 1446498 (98j:11046)
  • 15. J.-M. Couveignes.
    Isomorphisms between Artin-Schreier towers.
    Mathematics of Computation, 69(232):1625-1631, 2000. MR 1680863 (2003a:11157)
  • 16. 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.
    Available at http://www.lix.polytechnique.fr/Labo/Francois.Morain/.
  • 17. J.-M. Couveignes and T. Henocq.
    Action of modular correspondences around CM points.
    In C. Fieker and D. R. Kohel, editors, Algorithmic Number Theory, volume 2369 of Lecture Notes in Computer Science, pages 234-243. Springer-Verlag, 2002.
    Proceedings of the 5th International Symposium, ANTS-V, Sydney, Australia, July 2002. MR 2041087 (2005b:11077)
  • 18. J.-M. Couveignes and F. Morain.
    Schoof's algorithm and isogeny cycles.
    In L. Adleman and M.-D. Huang, editors, Algorithmic Number Theory, volume 877 of Lecture Notes in Computer Science, pages 43-58. Springer-Verlag, 1994.
    1st Algorithmic Number Theory Symposium, Cornell University, May 6-9, 1994. MR 1322711 (95m:11147)
  • 19. L. Dewaghe.
    Isogénie entre courbes elliptiques.
    Utilitas Mathematica, 55:123-127, 1999. MR 1685678 (2000b:14034)
  • 20. C. Doche, T. Icart, and D. R. Kohel.
    Efficient scalar multiplication by isogeny decompositions.
    Cryptology ePrint Archive, Report 2005/420, 2005.
    http://eprint.iacr.org/.
  • 21. N. D. Elkies.
    Explicit isogenies.
    Manuscript, 1992.
  • 22. 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. MR 1486831 (99a:11078)
  • 23. M. Fouquet and F. Morain.
    Isogeny volcanoes and the SEA algorithm.
    In C. Fieker and D. R. Kohel, editors, Algorithmic Number Theory, volume 2369 of Lecture Notes in Computer Science, pages 276-291. Springer-Verlag, 2002.
    Proceedings of the 5th International Symposium, ANTS-V, Sydney, Australia, July 2002. MR 2041091 (2005c:11077)
  • 24. S. Galbraith.
    Constructing isogenies between elliptic curves over finite fields.
    Journal of Computational Mathematics, 2:118-138, 1999. MR 1728955 (2001k:11113)
  • 25. S. D. Galbraith, F. Hess, and N. P. Smart.
    Extending the GHS Weil descent attack.
    In Advances in cryptology--EUROCRYPT 2002 (Amsterdam), volume 2332 of Lecture Notes in Computer Science, pages 29-44. Springer, Berlin, 2002. MR 1975526 (2004f:94060)
  • 26. J. von zur Gathen and J. Gerhard.
    Modern computer algebra.
    Cambridge University Press, 1999. MR 1689167 (2000j:68205)
  • 27. H. Gunji.
    The Hasse invariant and $ p$-division points of an elliptic curve.
    Arch. Math., 27(2):148-158, 1976. MR 0412198 (54:325)
  • 28. J. Gutierrez and T. Recio.
    A practical implementation of two rational function decomposition algorithms.
    In Proceedings ISSAC'92, pages 152-157. ACM, 1992.
  • 29. G. Hanrot, M. Quercia, and P. Zimmermann.
    The middle product algorithm, I. Speeding up the division and square root of power series.
    Applicable Algebra in Engineering, Communication and Computing, 14(6):415-438, 2004. MR 2042800 (2005a:65003)
  • 30. D. Jao, S. D. Miller, and R. Venkatesan.
    Do all elliptic curves of the same order have the same difficulty of discrete log?
    In Bimal Roy, editor, Advances in Cryptology - ASIACRYPT 2005, volume 3788 of Lecture Notes in Computer Science, pages 21-40, 2005.
    11th International Conference on the Theory and Application of Cryptology and Information Security, Chennai, India, December 4-8, 2005. MR 2236725 (2007e:94060)
  • 31. A. Joux and R. Lercier.
    Counting points on elliptic curves in medium characteristic.
    Cryptology ePrint Archive, Report 2006/176, 2006.
    http://eprint.iacr.org/.
  • 32. E. Kaltofen and V. Shoup.
    Subquadratic-time factoring of polynomials over finite fields.
    Mathematics of Computation, 67(223):1179-1197, 1998. MR 1459389 (99m:68097)
  • 33. K. S. Kedlaya.
    Counting points on hyperelliptic curves using Monsky-Washnitzer cohomology.
    Journal of the Ramanujan Mathematical Society, 16(4):323-338, 2001. MR 1877805 (2002m:14019)
  • 34. D. Kohel.
    Endomorphism rings of elliptic curves over finite fields.
    Ph.D. thesis, University of California at Berkeley, 1996.
  • 35. H. T. Kung.
    On computing reciprocals of power series.
    Numerische Mathematik, 22:341-348, 1974. MR 0351045 (50:3536)
  • 36. R. Lercier.
    Computing isogenies in $ {F}_{2^n}$.
    In H. Cohen, editor, Algorithmic Number Theory, volume 1122 of Lecture Notes in Computer Science, pages 197-212. Springer Verlag, 1996.
    Proceedings of the Second International Symposium, ANTS-II, Talence, France, May 1996. MR 1446512 (98d:11069)
  • 37. R. Lercier.
    Algorithmique des courbes elliptiques dans les corps finis.
    Thèse, École polytechnique, June 1997.
  • 38. R. Lercier and F. Morain.
    Computing isogenies between elliptic curves over $ {F}_{p^n}$ using Couveignes's algorithm.
    Mathematics of Computation, 69(229):351-370, January 2000. MR 1642770 (2001a:11101)
  • 39. F. Morain.
    Calcul du nombre de points sur une courbe elliptique dans un corps fini : aspects algorithmiques.
    Journal de Théorie des Nombres de Bordeaux, 7(1):255-282, 1995. MR 1413579 (97i:11069)
  • 40. 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.
  • 41. A. Rostovtsev and A. Stolbunov.
    Public-key cryptosystem based on isogenies.
    Cryptology ePrint Archive, Report 2006/145, 2006.
    http://eprint.iacr.org/.
  • 42. T. Satoh.
    The canonical lift of an ordinary elliptic curve over a finite field and its point counting.
    Journal of the Ramanujan Mathematical Society, 15:247-270, 2000. MR 1801221 (2001j:11049)
  • 43. A. Schönhage.
    The fundamental theorem of algebra in terms of computational complexity.
    Technical report, Mathematisches Institut der Universität Tübingen, 1982.
    Preliminary report.
  • 44. A. Schönhage and V. Strassen.
    Schnelle Multiplikation großer Zahlen.
    Computing, 7:281-292, 1971. MR 0292344 (45:1431)
  • 45. R. Schoof.
    Counting points on elliptic curves over finite fields.
    Journal de Théorie des Nombres de Bordeaux, 7(1):219-254, 1995. MR 1413578 (97i:11070)
  • 46. V. Shoup.
    A new polynomial factorization algorithm and its implementation.
    Journal of Symbolic Computation, 20(4):363-397, 1995. MR 1384454 (97d:12011)
  • 47. V. Shoup.
    The Number Theory Library.
    1996-2005.
    http://www.shoup.net/ntl.
  • 48. M. Sieveking.
    An algorithm for division of powerseries.
    Computing, 10:153-156, 1972. MR 0312701 (47:1257)
  • 49. J. H. Silverman.
    The arithmetic of elliptic curves, volume 106 of Graduate Texts in Mathematics.
    Springer, 1986. MR 817210 (87g:11070)
  • 50. J. H. Silverman.
    Advanced topics in the arithmetic of elliptic curves, volume 151 of Graduate Texts in Mathematics.
    Springer, 1994. MR 1312368 (96b:11074)
  • 51. N. P. Smart.
    An analysis of Goubin's Refined Power Analysis Attack.
    In Cryptographic Hardware and Embedded Systems - CHES 2003, volume 2779 of Lecture Notes in Computer Science, pages 281-290, Berlin, 2003. Springer.
  • 52. H. M. Stark.
    Class-numbers of complex quadratic fields.
    In W. Kuyk, editor, Modular functions of one variable I, volume 320 of Lecture Notes in Mathematics, pages 155-174. Springer Verlag, 1973.
    Proceedings International Summer School University of Antwerp, RUCA, July 17-August 3, 1972. MR 0344225 (49:8965)
  • 53. E. Teske.
    An elliptic trapdoor system.
    Journal of Cryptology, 19(1):115-133, 2006. MR 2210901 (2006k:94116)
  • 54. J. Vélu.
    Isogénies entre courbes elliptiques.
    Comptes-Rendus de l'Académie des Sciences, Série I, 273:238-241, juillet 1971.
  • 55. R. Zippel.
    Rational function decomposition.
    In Stephen M. Watt, editor, Symbolic and algebraic computation, pages 1-6, New York, 1991. ACM Press.
    Proceedings of ISSAC'91, Bonn, Germany.

Similar Articles

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

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


Additional Information

A. Bostan
Affiliation: Algorithms Project, INRIA Rocquencourt, 78153 Le Chesnay, France
Email: Alin.Bostan@inria.fr

F. Morain
Affiliation: Projet TANC, Pôle Commun de Recherche en Informatique du Plateau de Saclay, CNRS, École polytechnique, INRIA, Université Paris-Sud. The author is on leave from the French Department of Defense, Délégation Générale pour l’Armement.
Email: morain@lix.polytechnique.fr

B. Salvy
Affiliation: Algorithms Project, INRIA Rocquencourt, 78153 Le Chesnay, France
Email: Bruno.Salvy@inria.fr

É. Schost
Affiliation: Department of Computer Science, Room 415, Middlesex College, University of Western Ontario, London, Ontario, N6A 5B7, Canada
Email: eschost@uwo.ca

DOI: https://doi.org/10.1090/S0025-5718-08-02066-8
Keywords: Fast algorithms, elliptic curves, finite fields, isogenies, Schoof-Elkies-Atkin algorithm, Newton iteration
Received by editor(s): September 5, 2006
Received by editor(s) in revised form: April 3, 2007
Published electronically: January 18, 2008
Article copyright: © Copyright 2008 American Mathematical Society

American Mathematical Society