Fast algorithms for computing isogenies between elliptic curves

Bostan, A.; Morain, F.; Salvy, B.; Schost, É.

doi:10.1090/S0025-5718-08-02066-8

Fast algorithms for computing isogenies between elliptic curves
HTML articles powered by AMS MathViewer

by A. Bostan, F. Morain, B. Salvy and É. Schost;

Math. Comp. 77 (2008), 1755-1778

DOI: https://doi.org/10.1090/S0025-5718-08-02066-8

Published electronically: January 18, 2008

PDF | Request permission

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

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, DOI 10.1006/jsco.1995.1030
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.
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, DOI 10.1006/jsco.1998.0216
D. J. Bernstein. Removing redundancy in high-precision Newton iteration, 2000. Available on-line at http://cr.yp.to/fastnewton.html.
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
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-London, 1976, pp. 151–176. MR 423869
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, DOI 10.1016/0196-6774(80)90013-9
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 520733, DOI 10.1145/322092.322099
Eric Brier and Marc Joye, Fast point multiplication on elliptic curves through isogenies, Applied algebra, algebraic algorithms and error-correcting codes (Toulouse, 2003) Lecture Notes in Comput. Sci., vol. 2643, Springer, Berlin, 2003, pp. 43–50. MR 2042411, DOI 10.1007/3-540-44828-4_{6}
David G. Cantor and Erich Kaltofen, On fast multiplication of polynomials over arbitrary algebras, Acta Inform. 28 (1991), no. 7, 693–701. MR 1129288, DOI 10.1007/BF01178683
L. S. Charlap, R. Coley, and D. P. Robbins. Enumeration of rational points on elliptic curves over finite fields. Manuscript, 1991.
S. Cook. On the minimum computation time of functions. Ph.D. thesis, Harvard University, 1966.
J.-M. Couveignes. Quelques calculs en théorie des nombres. Thèse, Université de Bordeaux I, July 1994.
Jean-Marc Couveignes, Computing $l$-isogenies using the $p$-torsion, Algorithmic number theory (Talence, 1996) Lecture Notes in Comput. Sci., vol. 1122, Springer, Berlin, 1996, pp. 59–65. MR 1446498, DOI 10.1007/3-540-61581-4_{4}1
Jean-Marc Couveignes, Isomorphisms between Artin-Schreier towers, Math. Comp. 69 (2000), no. 232, 1625–1631. MR 1680863, DOI 10.1090/S0025-5718-00-01193-5
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/.
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, DOI 10.1007/3-540-45455-1_{1}9
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, DOI 10.1007/3-540-58691-1_{4}2
L. Dewaghe, Isogénie entre courbes elliptiques, Util. Math. 55 (1999), 123–127 (French, with English and French summaries). MR 1685678
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/.
N. D. Elkies. Explicit isogenies. Manuscript, 1992.
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, DOI 10.1090/amsip/007/03
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, DOI 10.1007/3-540-45455-1_{2}3
Steven D. Galbraith, Constructing isogenies between elliptic curves over finite fields, LMS J. Comput. Math. 2 (1999), 118–138. MR 1728955, DOI 10.1112/S1461157000000097
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, DOI 10.1007/3-540-46035-7_{3}
Joachim von zur Gathen and Jürgen Gerhard, Modern computer algebra, Cambridge University Press, New York, 1999. MR 1689167
Hiroshi Gunji, The Hasse invariant and $p$-division points of an elliptic curve, Arch. Math. (Basel) 27 (1976), no. 2, 148–158. MR 412198, DOI 10.1007/BF01224654
J. Gutierrez and T. Recio. A practical implementation of two rational function decomposition algorithms. In Proceedings ISSAC’92, pages 152–157. ACM, 1992.
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, DOI 10.1007/s00200-003-0144-2
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, DOI 10.1007/11593447_{2}
A. Joux and R. Lercier. Counting points on elliptic curves in medium characteristic. Cryptology ePrint Archive, Report 2006/176, 2006. http://eprint.iacr.org/.
Erich Kaltofen and Victor Shoup, Subquadratic-time factoring of polynomials over finite fields, Math. Comp. 67 (1998), no. 223, 1179–1197. MR 1459389, DOI 10.1090/S0025-5718-98-00944-2
Kiran S. Kedlaya, Counting points on hyperelliptic curves using Monsky-Washnitzer cohomology, J. Ramanujan Math. Soc. 16 (2001), no. 4, 323–338. MR 1877805
D. Kohel. Endomorphism rings of elliptic curves over finite fields. Ph.D. thesis, University of California at Berkeley, 1996.
H. T. Kung, On computing reciprocals of power series, Numer. Math. 22 (1974), 341–348. MR 351045, DOI 10.1007/BF01436917
Reynald Lercier, Computing isogenies in $\textbf {F}_{2^n}$, Algorithmic number theory (Talence, 1996) Lecture Notes in Comput. Sci., vol. 1122, Springer, Berlin, 1996, pp. 197–212. MR 1446512, DOI 10.1007/3-540-61581-4_{5}5
R. Lercier. Algorithmique des courbes elliptiques dans les corps finis. Thèse, École polytechnique, June 1997.
R. Lercier and F. Morain, Computing isogenies between elliptic curves over $\mathbf F_{p^n}$ using Couveignes’s algorithm, Math. Comp. 69 (2000), no. 229, 351–370. MR 1642770, DOI 10.1090/S0025-5718-99-01081-9
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
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.
A. Rostovtsev and A. Stolbunov. Public-key cryptosystem based on isogenies. Cryptology ePrint Archive, Report 2006/145, 2006. http://eprint.iacr.org/.
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
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.
A. Schönhage and V. Strassen, Schnelle Multiplikation grosser Zahlen, Computing (Arch. Elektron. Rechnen) 7 (1971), 281–292 (German, with English summary). MR 292344, DOI 10.1007/bf02242355
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
Victor Shoup, A new polynomial factorization algorithm and its implementation, J. Symbolic Comput. 20 (1995), no. 4, 363–397. MR 1384454, DOI 10.1006/jsco.1995.1055
V. Shoup. The Number Theory Library. 1996–2005. http://www.shoup.net/ntl.
M. Sieveking, An algorithm for division of powerseries, Computing (Arch. Elektron. Rechnen) 10 (1972), 153–156 (English, with German summary). MR 312701, DOI 10.1007/bf02242389
Joseph H. Silverman, The arithmetic of elliptic curves, Graduate Texts in Mathematics, vol. 106, Springer-Verlag, New York, 1986. MR 817210, DOI 10.1007/978-1-4757-1920-8
Joseph H. Silverman, Advanced topics in the arithmetic of elliptic curves, Graduate Texts in Mathematics, vol. 151, Springer-Verlag, New York, 1994. MR 1312368, DOI 10.1007/978-1-4612-0851-8
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.
H. M. Stark, Class-numbers of complex quadratic fields, Modular functions of one variable, I (Proc. Internat. Summer School, Univ. Antwerp, Antwerp, 1972) Lecture Notes in Math., Vol. 320, Springer, Berlin-New York, 1973, pp. 153–174. MR 344225
Edlyn Teske, An elliptic curve trapdoor system, J. Cryptology 19 (2006), no. 1, 115–133. MR 2210901, DOI 10.1007/s00145-004-0328-3
J. Vélu. Isogénies entre courbes elliptiques. Comptes-Rendus de l’Académie des Sciences, Série I, 273:238–241, juillet 1971.
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.