{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,17]],"date-time":"2026-06-17T16:40:58Z","timestamp":1781714458936,"version":"3.54.5"},"reference-count":55,"publisher":"American Mathematical Society (AMS)","issue":"263","license":[{"start":{"date-parts":[[2009,1,18]],"date-time":"2009-01-18T00:00:00Z","timestamp":1232236800000},"content-version":"am","delay-in-days":366,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"<p>\n                    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\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"script l\">\n                        <mml:semantics>\n                          <mml:mi>\n                            \u2113\n                            \n                          <\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">\\ell<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    (\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"script l\">\n                        <mml:semantics>\n                          <mml:mi>\n                            \u2113\n                            \n                          <\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">\\ell<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    different from the characteristic) in time quasi-linear with respect to\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"script l\">\n                        <mml:semantics>\n                          <mml:mi>\n                            \u2113\n                            \n                          <\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">\\ell<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    . This is based in particular on fast algorithms for power series expansion of the Weierstrass\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"normal script upper P\">\n                        <mml:semantics>\n                          <mml:mi mathvariant=\"normal\">\n                            \u2118\n                            \n                          <\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">\\wp<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    -function and related functions.\n                  <\/p>","DOI":"10.1090\/s0025-5718-08-02066-8","type":"journal-article","created":{"date-parts":[[2008,4,22]],"date-time":"2008-04-22T17:24:54Z","timestamp":1208885094000},"page":"1755-1778","source":"Crossref","is-referenced-by-count":44,"title":["Fast algorithms for computing isogenies between elliptic curves"],"prefix":"10.1090","volume":"77","author":[{"given":"A.","family":"Bostan","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"F.","family":"Morain","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"B.","family":"Salvy","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"\u00c9.","family":"Schost","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"14","published-online":{"date-parts":[[2008,1,18]]},"reference":[{"issue":"6","key":"1","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1006\/jsco.1995.1030","article-title":"A rational function decomposition algorithm by near-separated polynomials","volume":"19","author":"Alonso, Cesar","year":"1995","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"key":"2","unstructured":"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."},{"issue":"3","key":"3","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1006\/jsco.1998.0216","article-title":"Composing power series over a finite ring in essentially linear time","volume":"26","author":"Bernstein, Daniel J.","year":"1998","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"key":"4","unstructured":"D. J. Bernstein. Removing redundancy in high-precision Newton iteration, 2000. Available on-line at http:\/\/cr.yp.to\/fastnewton.html."},{"key":"5","series-title":"London Mathematical Society Lecture Note Series","isbn-type":"print","volume-title":"Elliptic curves in cryptography","volume":"265","author":"Blake, I. F.","year":"2000","ISBN":"https:\/\/id.crossref.org\/isbn\/0521653746"},{"key":"6","first-page":"151","article-title":"Multiple-precision zero-finding methods and the complexity of elementary function evaluation","author":"Brent, Richard P.","year":"1976"},{"issue":"3","key":"7","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1016\/0196-6774(80)90013-9","article-title":"Fast solution of Toeplitz systems of equations and computation of Pad\u00e9 approximants","volume":"1","author":"Brent, Richard P.","year":"1980","journal-title":"J. Algorithms","ISSN":"https:\/\/id.crossref.org\/issn\/0196-6774","issn-type":"print"},{"issue":"4","key":"8","doi-asserted-by":"publisher","first-page":"581","DOI":"10.1145\/322092.322099","article-title":"Fast algorithms for manipulating formal power series","volume":"25","author":"Brent, R. P.","year":"1978","journal-title":"J. Assoc. Comput. Mach.","ISSN":"https:\/\/id.crossref.org\/issn\/0004-5411","issn-type":"print"},{"key":"9","isbn-type":"print","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/3-540-44828-4_6","article-title":"Fast point multiplication on elliptic curves through isogenies","author":"Brier, Eric","year":"2003","ISBN":"https:\/\/id.crossref.org\/isbn\/3540401113"},{"issue":"7","key":"10","doi-asserted-by":"publisher","first-page":"693","DOI":"10.1007\/BF01178683","article-title":"On fast multiplication of polynomials over arbitrary algebras","volume":"28","author":"Cantor, David G.","year":"1991","journal-title":"Acta Inform.","ISSN":"https:\/\/id.crossref.org\/issn\/0001-5903","issn-type":"print"},{"key":"11","unstructured":"L. S. Charlap, R. Coley, and D. P. Robbins. Enumeration of rational points on elliptic curves over finite fields. Manuscript, 1991."},{"key":"12","unstructured":"S. Cook. On the minimum computation time of functions. Ph.D. thesis, Harvard University, 1966."},{"key":"13","unstructured":"J.-M. Couveignes. Quelques calculs en th\u00e9orie des nombres. Th\u00e8se, Universit\u00e9 de Bordeaux I, July 1994."},{"key":"14","isbn-type":"print","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/3-540-61581-4_41","article-title":"Computing \ud835\udc59-isogenies using the \ud835\udc5d-torsion","author":"Couveignes, Jean-Marc","year":"1996","ISBN":"https:\/\/id.crossref.org\/isbn\/3540615814"},{"issue":"232","key":"15","doi-asserted-by":"publisher","first-page":"1625","DOI":"10.1090\/S0025-5718-00-01193-5","article-title":"Isomorphisms between Artin-Schreier towers","volume":"69","author":"Couveignes, Jean-Marc","year":"2000","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"16","unstructured":"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\/."},{"key":"17","isbn-type":"print","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1007\/3-540-45455-1_19","article-title":"Action of modular correspondences around CM points","author":"Couveignes, Jean-Marc","year":"2002","ISBN":"https:\/\/id.crossref.org\/isbn\/3540438637"},{"key":"18","isbn-type":"print","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/3-540-58691-1_42","article-title":"Schoof\u2019s algorithm and isogeny cycles","author":"Couveignes, Jean-Marc","year":"1994","ISBN":"https:\/\/id.crossref.org\/isbn\/3540586911"},{"key":"19","first-page":"123","article-title":"Isog\u00e9nie entre courbes elliptiques","volume":"55","author":"Dewaghe, L.","year":"1999","journal-title":"Util. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0315-3681","issn-type":"print"},{"key":"20","unstructured":"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\/."},{"key":"21","unstructured":"N. D. Elkies. Explicit isogenies. Manuscript, 1992."},{"key":"22","isbn-type":"print","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1090\/amsip\/007\/03","article-title":"Elliptic and modular curves over finite fields and related computational issues","author":"Elkies, Noam D.","year":"1998","ISBN":"https:\/\/id.crossref.org\/isbn\/082180880X"},{"key":"23","isbn-type":"print","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1007\/3-540-45455-1_23","article-title":"Isogeny volcanoes and the SEA algorithm","author":"Fouquet, Mireille","year":"2002","ISBN":"https:\/\/id.crossref.org\/isbn\/3540438637"},{"key":"24","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1112\/S1461157000000097","article-title":"Constructing isogenies between elliptic curves over finite fields","volume":"2","author":"Galbraith, Steven D.","year":"1999","journal-title":"LMS J. Comput. Math."},{"key":"25","isbn-type":"print","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/3-540-46035-7_3","article-title":"Extending the GHS Weil descent attack","author":"Galbraith, Steven D.","year":"2002","ISBN":"https:\/\/id.crossref.org\/isbn\/3540435530"},{"key":"26","isbn-type":"print","volume-title":"Modern computer algebra","author":"von zur Gathen, Joachim","year":"1999","ISBN":"https:\/\/id.crossref.org\/isbn\/0521641764"},{"issue":"2","key":"27","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1007\/BF01224654","article-title":"The Hasse invariant and \ud835\udc5d-division points of an elliptic curve","volume":"27","author":"Gunji, Hiroshi","year":"1976","journal-title":"Arch. Math. (Basel)","ISSN":"https:\/\/id.crossref.org\/issn\/0003-889X","issn-type":"print"},{"key":"28","doi-asserted-by":"crossref","unstructured":"J. Gutierrez and T. Recio. A practical implementation of two rational function decomposition algorithms. In Proceedings ISSAC\u201992, pages 152\u2013157. ACM, 1992.","DOI":"10.1145\/143242.143298"},{"issue":"6","key":"29","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1007\/s00200-003-0144-2","article-title":"The middle product algorithm. I","volume":"14","author":"Hanrot, Guillaume","year":"2004","journal-title":"Appl. Algebra Engrg. Comm. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0938-1279","issn-type":"print"},{"key":"30","isbn-type":"print","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/11593447_2","article-title":"Do all elliptic curves of the same order have the same difficulty of discrete log?","author":"Jao, David","year":"2005","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540306849"},{"key":"31","unstructured":"A. Joux and R. Lercier. Counting points on elliptic curves in medium characteristic. Cryptology ePrint Archive, Report 2006\/176, 2006. http:\/\/eprint.iacr.org\/."},{"issue":"223","key":"32","doi-asserted-by":"publisher","first-page":"1179","DOI":"10.1090\/S0025-5718-98-00944-2","article-title":"Subquadratic-time factoring of polynomials over finite fields","volume":"67","author":"Kaltofen, Erich","year":"1998","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"4","key":"33","first-page":"323","article-title":"Counting points on hyperelliptic curves using Monsky-Washnitzer cohomology","volume":"16","author":"Kedlaya, Kiran S.","year":"2001","journal-title":"J. Ramanujan Math. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/0970-1249","issn-type":"print"},{"key":"34","unstructured":"D. Kohel. Endomorphism rings of elliptic curves over finite fields. Ph.D. thesis, University of California at Berkeley, 1996."},{"key":"35","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1007\/BF01436917","article-title":"On computing reciprocals of power series","volume":"22","author":"Kung, H. T.","year":"1974","journal-title":"Numer. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0029-599X","issn-type":"print"},{"key":"36","isbn-type":"print","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1007\/3-540-61581-4_55","article-title":"Computing isogenies in \ud835\udc39_{2\u207f}","author":"Lercier, Reynald","year":"1996","ISBN":"https:\/\/id.crossref.org\/isbn\/3540615814"},{"key":"37","unstructured":"R. Lercier. Algorithmique des courbes elliptiques dans les corps finis. Th\u00e8se, \u00c9cole polytechnique, June 1997."},{"issue":"229","key":"38","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1090\/S0025-5718-99-01081-9","article-title":"Computing isogenies between elliptic curves over \ud835\udc05_{\ud835\udc29\u207f} using Couveignes\u2019s algorithm","volume":"69","author":"Lercier, R.","year":"2000","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"1","key":"39","doi-asserted-by":"publisher","first-page":"255","DOI":"10.5802\/jtnb.143","article-title":"Calcul du nombre de points sur une courbe elliptique dans un corps fini: aspects algorithmiques","volume":"7","author":"Morain, Fran\u00e7ois","year":"1995","journal-title":"J. Th\\'{e}or. Nombres Bordeaux","ISSN":"https:\/\/id.crossref.org\/issn\/1246-7405","issn-type":"print"},{"key":"40","unstructured":"V. M\u00fcller. Ein Algorithmus zur Bestimmung der Punktanzahl elliptischer Kurven \u00fcber endlichen K\u00f6rpern der Charakteristik gr\u00f6\u00dfer drei. Ph.D. thesis, Technischen Fakult\u00e4t der Universit\u00e4t des Saarlandes, 1995."},{"key":"41","unstructured":"A. Rostovtsev and A. Stolbunov. Public-key cryptosystem based on isogenies. Cryptology ePrint Archive, Report 2006\/145, 2006. http:\/\/eprint.iacr.org\/."},{"issue":"4","key":"42","first-page":"247","article-title":"The canonical lift of an ordinary elliptic curve over a finite field and its point counting","volume":"15","author":"Satoh, Takakazu","year":"2000","journal-title":"J. Ramanujan Math. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/0970-1249","issn-type":"print"},{"key":"43","unstructured":"A. Sch\u00f6nhage. The fundamental theorem of algebra in terms of computational complexity. Technical report, Mathematisches Institut der Universit\u00e4t T\u00fcbingen, 1982. Preliminary report."},{"key":"44","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/bf02242355","article-title":"Schnelle Multiplikation grosser Zahlen","volume":"7","author":"Sch\u00f6nhage, A.","year":"1971","journal-title":"Computing (Arch. Elektron. Rechnen)","ISSN":"https:\/\/id.crossref.org\/issn\/0010-485X","issn-type":"print"},{"issue":"1","key":"45","doi-asserted-by":"publisher","first-page":"219","DOI":"10.5802\/jtnb.142","article-title":"Counting points on elliptic curves over finite fields","volume":"7","author":"Schoof, Ren\u00e9","year":"1995","journal-title":"J. Th\\'{e}or. Nombres Bordeaux","ISSN":"https:\/\/id.crossref.org\/issn\/1246-7405","issn-type":"print"},{"issue":"4","key":"46","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1006\/jsco.1995.1055","article-title":"A new polynomial factorization algorithm and its implementation","volume":"20","author":"Shoup, Victor","year":"1995","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"key":"47","unstructured":"V. Shoup. The Number Theory Library. 1996\u20132005. http:\/\/www.shoup.net\/ntl."},{"key":"48","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/bf02242389","article-title":"An algorithm for division of powerseries","volume":"10","author":"Sieveking, M.","year":"1972","journal-title":"Computing (Arch. Elektron. Rechnen)","ISSN":"https:\/\/id.crossref.org\/issn\/0010-485X","issn-type":"print"},{"key":"49","series-title":"Graduate Texts in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-1920-8","volume-title":"The arithmetic of elliptic curves","volume":"106","author":"Silverman, Joseph H.","year":"1986","ISBN":"https:\/\/id.crossref.org\/isbn\/0387962034"},{"key":"50","series-title":"Graduate Texts in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0851-8","volume-title":"Advanced topics in the arithmetic of elliptic curves","volume":"151","author":"Silverman, Joseph H.","year":"1994","ISBN":"https:\/\/id.crossref.org\/isbn\/0387943285"},{"key":"51","doi-asserted-by":"crossref","unstructured":"N. P. Smart. An analysis of Goubin\u2019s Refined Power Analysis Attack. In Cryptographic Hardware and Embedded Systems \u2013 CHES 2003, volume 2779 of Lecture Notes in Computer Science, pages 281\u2013290, Berlin, 2003. Springer.","DOI":"10.1007\/978-3-540-45238-6_23"},{"key":"52","first-page":"153","article-title":"Class-numbers of complex quadratic fields","author":"Stark, H. M.","year":"1973"},{"issue":"1","key":"53","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/s00145-004-0328-3","article-title":"An elliptic curve trapdoor system","volume":"19","author":"Teske, Edlyn","year":"2006","journal-title":"J. Cryptology","ISSN":"https:\/\/id.crossref.org\/issn\/0933-2790","issn-type":"print"},{"key":"54","unstructured":"J. V\u00e9lu. Isog\u00e9nies entre courbes elliptiques. Comptes-Rendus de l\u2019Acad\u00e9mie des Sciences, S\u00e9rie I, 273:238\u2013241, juillet 1971."},{"key":"55","doi-asserted-by":"crossref","unstructured":"R. Zippel. Rational function decomposition. In Stephen M. Watt, editor, Symbolic and algebraic computation, pages 1\u20136, New York, 1991. ACM Press. Proceedings of ISSAC\u201991, Bonn, Germany.","DOI":"10.1145\/120694.120695"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2008-77-263\/S0025-5718-08-02066-8\/S0025-5718-08-02066-8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2008-77-263\/S0025-5718-08-02066-8\/S0025-5718-08-02066-8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T15:22:55Z","timestamp":1776784975000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2008-77-263\/S0025-5718-08-02066-8\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,1,18]]},"references-count":55,"journal-issue":{"issue":"263","published-print":{"date-parts":[[2008,7]]}},"alternative-id":["S0025-5718-08-02066-8"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-08-02066-8","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2008,1,18]]}}}