Mathematics of Computation

			Journals Home Search Author Info Subscribe Tech Support My Subscriptions Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

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
Posted: January 18, 2008
MathSciNet review: 2398793
Full-text PDF

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

1. Cesar Alonso, Jaime Gutierrez, and Tomas Recio, A rational function decomposition algorithm by near-separated polynomials, J. Symbolic Comput. 19 (1995), no. 6, 527–544. MR 1370620 (96j:13025), http://dx.doi.org/10.1006/jsco.1995.1030
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. Daniel J. Bernstein, Composing power series over a finite ring in essentially linear time, J. Symbolic Comput. 26 (1998), no. 3, 339–341. MR 1633872, http://dx.doi.org/10.1006/jsco.1998.0216
4. D. J. Bernstein.
Removing redundancy in high-precision Newton iteration, 2000.
Available on-line at http://cr.yp.to/fastnewton.html.
5. I. F. Blake, G. Seroussi, and N. P. Smart, Elliptic curves in cryptography, London Mathematical Society Lecture Note Series, vol. 265, Cambridge University Press, Cambridge, 2000. Reprint of the 1999 original. MR 1771549 (2001i:94048)
6. Richard P. Brent, Multiple-precision zero-finding methods and the complexity of elementary function evaluation, Analytic computational complexity (Proc. Sympos., Carnegie-Mellon Univ., Pittsburgh, Pa., 1975), Academic Press, New York, 1976, pp. 151–176. MR 0423869 (54 #11843)
7. Richard P. Brent, Fred G. Gustavson, and David Y. Y. Yun, Fast solution of Toeplitz systems of equations and computation of Padé approximants, J. Algorithms 1 (1980), no. 3, 259–295. MR 604867 (82d:65033), http://dx.doi.org/10.1016/0196-6774(80)90013-9
8. R. P. Brent and H. T. Kung, Fast algorithms for manipulating formal power series, J. Assoc. Comput. Mach. 25 (1978), no. 4, 581–595. MR 0520733 (58 #25090)
9. Eric Brier and Marc Joye, Fast point multiplication on elliptic curves through isogenies, (Toulouse, 2003) Lecture Notes in Comput. Sci., vol. 2643, Springer, Berlin, 2003, pp. 43–50. MR 2042411 (2005a:14029), http://dx.doi.org/10.1007/3-540-44828-4_6
10. David G. Cantor and Erich Kaltofen, On fast multiplication of polynomials over arbitrary algebras, Acta Inform. 28 (1991), no. 7, 693–701. MR 1129288 (92i:68068), http://dx.doi.org/10.1007/BF01178683
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. Jean-Marc Couveignes, Computing 𝑙-isogenies using the 𝑝-torsion, Algorithmic number theory (Talence, 1996) Lecture Notes in Comput. Sci., vol. 1122, Springer, Berlin, 1996, pp. 59–65. MR 1446498 (98j:11046)
15. Jean-Marc Couveignes, Isomorphisms between Artin-Schreier towers, Math. Comp. 69 (2000), no. 232, 1625–1631. MR 1680863 (2003a:11157), http://dx.doi.org/10.1090/S0025-5718-00-01193-5
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. Jean-Marc Couveignes and Thierry Henocq, Action of modular correspondences around CM points, Algorithmic number theory (Sydney, 2002) Lecture Notes in Comput. Sci., vol. 2369, Springer, Berlin, 2002, pp. 234–243. MR 2041087 (2005b:11077), http://dx.doi.org/10.1007/3-540-45455-1_19
18. 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)
19. L. Dewaghe, Isogénie entre courbes elliptiques, Util. Math. 55 (1999), 123–127 (French, with English and French summaries). 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. 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)
23. Mireille Fouquet and François Morain, Isogeny volcanoes and the SEA algorithm, Algorithmic number theory (Sydney, 2002) Lecture Notes in Comput. Sci., vol. 2369, Springer, Berlin, 2002, pp. 276–291. MR 2041091 (2005c:11077), http://dx.doi.org/10.1007/3-540-45455-1_23
24. Steven D. Galbraith, Constructing isogenies between elliptic curves over finite fields, LMS J. Comput. Math. 2 (1999), 118–138 (electronic). MR 1728955 (2001k:11113)
25. Steven D. Galbraith, Florian Hess, and Nigel P. Smart, Extending the GHS Weil descent attack, Advances in cryptology—EUROCRYPT 2002 (Amsterdam), Lecture Notes in Comput. Sci., vol. 2332, Springer, Berlin, 2002, pp. 29–44. MR 1975526 (2004f:94060), http://dx.doi.org/10.1007/3-540-46035-7_3
26. Joachim von zur Gathen and Jürgen Gerhard, Modern computer algebra, Cambridge University Press, New York, 1999. MR 1689167 (2000j:68205)
27. Hiroshi Gunji, The Hasse invariant and 𝑝-division points of an elliptic curve, Arch. Math. (Basel) 27 (1976), no. 2, 148–158. 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. Guillaume Hanrot, Michel Quercia, and Paul Zimmermann, The middle product algorithm. I, Appl. Algebra Engrg. Comm. Comput. 14 (2004), no. 6, 415–438. MR 2042800 (2005a:65003), http://dx.doi.org/10.1007/s00200-003-0144-2
30. David Jao, Stephen D. Miller, and Ramarathnam Venkatesan, Do all elliptic curves of the same order have the same difficulty of discrete log?, Advances in cryptology—ASIACRYPT 2005, Lecture Notes in Comput. Sci., vol. 3788, Springer, Berlin, 2005, pp. 21–40. MR 2236725 (2007e:94060), http://dx.doi.org/10.1007/11593447_2
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. Erich Kaltofen and Victor Shoup, Subquadratic-time factoring of polynomials over finite fields, Math. Comp. 67 (1998), no. 223, 1179–1197. MR 1459389 (99m:68097), http://dx.doi.org/10.1090/S0025-5718-98-00944-2
33. Kiran S. Kedlaya, Counting points on hyperelliptic curves using Monsky-Washnitzer cohomology, J. Ramanujan Math. Soc. 16 (2001), no. 4, 323–338. 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, Numer. Math. 22 (1974), 341–348. MR 0351045 (50 #3536)
36. Reynald Lercier, Computing isogenies in 𝐹_{2ⁿ}, Algorithmic number theory (Talence, 1996) Lecture Notes in Comput. Sci., vol. 1122, Springer, Berlin, 1996, pp. 197–212. 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 𝐅_{𝐩ⁿ} using Couveignes’s algorithm, Math. Comp. 69 (2000), no. 229, 351–370. MR 1642770 (2001a:11101), http://dx.doi.org/10.1090/S0025-5718-99-01081-9
39. 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)
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. Takakazu Satoh, The canonical lift of an ordinary elliptic curve over a finite field and its point counting, J. Ramanujan Math. Soc. 15 (2000), no. 4, 247–270. 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 grosser Zahlen, Computing (Arch. Elektron. Rechnen) 7 (1971), 281–292 (German, with English summary). MR 0292344 (45 #1431)
45. 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)
46. Victor Shoup, A new polynomial factorization algorithm and its implementation, J. Symbolic Comput. 20 (1995), no. 4, 363–397. MR 1384454 (97d:12011), http://dx.doi.org/10.1006/jsco.1995.1055
47. V. Shoup.
The Number Theory Library.
1996-2005.
http://www.shoup.net/ntl.
48. M. Sieveking, An algorithm for division of powerseries, Computing (Arch. Elektron. Rechnen) 10 (1972), 153–156 (English, with German summary). MR 0312701 (47 #1257)
49. Joseph H. Silverman, The arithmetic of elliptic curves, Graduate Texts in Mathematics, vol. 106, Springer-Verlag, New York, 1986. MR 817210 (87g:11070)
50. Joseph H. Silverman, Advanced topics in the arithmetic of elliptic curves, Graduate Texts in Mathematics, vol. 151, Springer-Verlag, New York, 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, Modular functions of one variable, I (Proc. Internat. Summer School, Univ. Antwerp, Antwerp, 1972), Springer, Berlin, 1973, pp. 153–174. Lecture Notes in Mathematics, Vol. 320. MR 0344225 (49 #8965)
53. Edlyn Teske, An elliptic curve trapdoor system, J. Cryptology 19 (2006), no. 1, 115–133. MR 2210901 (2006k:94116), http://dx.doi.org/10.1007/s00145-004-0328-3
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.

	Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
\|