{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T18:19:26Z","timestamp":1776795566565,"version":"3.51.2"},"reference-count":26,"publisher":"American Mathematical Society (AMS)","issue":"281","license":[{"start":{"date-parts":[[2013,7,24]],"date-time":"2013-07-24T00:00:00Z","timestamp":1374624000000},"content-version":"am","delay-in-days":365,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"

\n Isogeny volcanoes are graphs whose vertices are elliptic curves and whose edges are\n \n \n \n \n \u2113\n \n <\/mml:mi>\n \\ell<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n -isogenies. Algorithms allowing to travel on these graphs were developed by Kohel in his thesis (1996) and later on, by Fouquet and Morain (2001). However, up to now, no method was known, to predict, before taking a step on the volcano, the direction of this step. Hence, in Kohel\u2019s and Fouquet-Morain\u2019s algorithms, many steps are taken before choosing the right direction. In particular, ascending or horizontal isogenies are usually found using a trial-and-error approach. In this paper, we propose an alternative method that efficiently finds all points\n \n \n \n P<\/mml:mi>\n P<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n of order\n \n \n \n \n \u2113\n \n <\/mml:mi>\n \\ell<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n such that the subgroup generated by\n \n \n \n P<\/mml:mi>\n P<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n is the kernel of a horizontal or an ascending isogeny. In many cases, our method is faster than previous methods. This is an extended version of a paper published in the proceedings of ANTS 2010. In addition, we treat the case of 2-isogeny volcanoes and we derive from the group structure of the curve and the pairing a new invariant of the endomorphism class of an elliptic curve. Our benchmarks show that the resulting algorithm for endomorphism ring computation is faster than Kohel\u2019s method for computing the\n \n \n \n \n \u2113\n \n <\/mml:mi>\n \\ell<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n -adic valuation of the conductor of the endomorphism ring for small\n \n \n \n \n \u2113\n \n <\/mml:mi>\n \\ell<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n .\n <\/p>","DOI":"10.1090\/s0025-5718-2012-02622-6","type":"journal-article","created":{"date-parts":[[2012,7,24]],"date-time":"2012-07-24T10:20:18Z","timestamp":1343125218000},"page":"581-603","source":"Crossref","is-referenced-by-count":16,"title":["Pairing the volcano"],"prefix":"10.1090","volume":"82","author":[{"given":"Sorina","family":"Ionica","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Antoine","family":"Joux","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"14","published-online":{"date-parts":[[2012,7,24]]},"reference":[{"key":"1","isbn-type":"print","doi-asserted-by":"publisher","first-page":"282","DOI":"10.1007\/978-3-540-79456-1_19","article-title":"Computing Hilbert class polynomials","author":"Belding, Juliana","year":"2008","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540794554"},{"issue":"5","key":"2","doi-asserted-by":"publisher","first-page":"815","DOI":"10.1016\/j.jnt.2009.11.003","article-title":"Computing the endomorphism ring of an ordinary elliptic curve over a finite field","volume":"131","author":"Bisson, Gaetan","year":"2011","journal-title":"J. Number Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0022-314X","issn-type":"print"},{"key":"3","unstructured":"R. Broker, K. Lauter, and A. Sutherland. Computing modular polynomials with the chinese remainder theorem. http:\/\/arxiv.org\/abs\/1001.0402, 2009."},{"key":"4","unstructured":"D. Charles. On the existence of distortion maps on ordinary curves. http:\/\/eprint.iacr.org\/2006\/128."},{"key":"5","series-title":"A Wiley-Interscience Publication","isbn-type":"print","volume-title":"Primes of the form $x^2 + ny^2$","author":"Cox, David A.","year":"1989","ISBN":"https:\/\/id.crossref.org\/isbn\/0471506540"},{"key":"6","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1007\/BF02940746","article-title":"Die Typen der Multiplikatorenringe elliptischer Funktionenk\u00f6rper","volume":"14","author":"Deuring, Max","year":"1941","journal-title":"Abh. Math. Sem. Hansischen Univ.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5858","issn-type":"print"},{"key":"7","unstructured":"M. Fouquet. Anneau d\u2019endomorphismes et cardinalit\u00e9 des courbes elliptiques: aspects algorithmiques. PhD thesis, Ecole Polytechnique, 2001."},{"key":"8","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":"9","isbn-type":"print","first-page":"128","article-title":"Applications of arithmetical geometry to cryptographic constructions","author":"Frey, Gerhard","year":"2001","ISBN":"https:\/\/id.crossref.org\/isbn\/3540411097"},{"key":"10","doi-asserted-by":"crossref","unstructured":"P. Grabher, J. Gro\u00dfsch\u00e4dl, and D. Page. On software parallel implementation of cryptographic pairings. In Selected Areas in Cryptography 2008, volume 5381 of Lecture Notes in Computer Science, pages 35\u201350. Springer, 2009.","DOI":"10.1007\/978-3-642-04159-4_3"},{"key":"11","isbn-type":"print","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/978-3-642-14518-6_18","article-title":"Pairing the volcano","author":"Ionica, Sorina","year":"2010","ISBN":"https:\/\/id.crossref.org\/isbn\/9783642145179"},{"issue":"4","key":"12","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/s00145-003-0052-4","article-title":"Separating decision Diffie-Hellmann from computational Diffie-Hellman in cryptographic groups","volume":"16","author":"Joux, Antoine","year":"2003","journal-title":"J. Cryptology","ISSN":"https:\/\/id.crossref.org\/issn\/0933-2790","issn-type":"print"},{"issue":"2","key":"13","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1006\/jnth.1996.0015","article-title":"Complex multiplication structure of elliptic curves","volume":"56","author":"Lenstra, H. W., Jr.","year":"1996","journal-title":"J. Number Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0022-314X","issn-type":"print"},{"key":"14","isbn-type":"print","volume-title":"Endomorphism rings of elliptic curves over finite fields","author":"Kohel, David Russell","year":"1996","ISBN":"https:\/\/id.crossref.org\/isbn\/9780591321234"},{"key":"15","isbn-type":"print","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1142\/9789812793430_0002","article-title":"Computing endomorphism rings of Jacobians of genus 2 curves over finite fields","author":"Freeman, David","year":"2008","ISBN":"https:\/\/id.crossref.org\/isbn\/9789812793423"},{"issue":"4","key":"16","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/s00145-004-0315-8","article-title":"The Weil pairing, and its efficient calculation","volume":"17","author":"Miller, Victor S.","year":"2004","journal-title":"J. Cryptology","ISSN":"https:\/\/id.crossref.org\/issn\/0933-2790","issn-type":"print"},{"issue":"2","key":"17","doi-asserted-by":"publisher","first-page":"739","DOI":"10.1016\/j.amc.2005.10.020","article-title":"An algorithm to compute volcanoes of 2-isogenies of elliptic curves over finite fields","volume":"176","author":"Miret, J.","year":"2006","journal-title":"Appl. Math. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0096-3003","issn-type":"print"},{"issue":"1","key":"18","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/j.amc.2007.05.037","article-title":"Computing the height of volcanoes of \ud835\udc59-isogenies of elliptic curves over finite fields","volume":"196","author":"Miret, J.","year":"2008","journal-title":"Appl. Math. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0096-3003","issn-type":"print"},{"key":"19","volume-title":"An FFT extension of the elliptic curve method of factorization","author":"Montgomery, Peter Lawrence","year":"1992"},{"issue":"179","key":"20","doi-asserted-by":"publisher","first-page":"301","DOI":"10.2307\/2008268","article-title":"A note on elliptic curves over finite fields","volume":"49","author":"R\u00fcck, Hans-Georg","year":"1987","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"1","key":"21","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"},{"key":"22","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":"23","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"},{"issue":"273","key":"24","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1090\/S0025-5718-2010-02373-7","article-title":"Computing Hilbert class polynomials with the Chinese remainder theorem","volume":"80","author":"Sutherland, Andrew V.","year":"2011","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"25","first-page":"A238--A241","article-title":"Isog\u00e9nies entre courbes elliptiques","volume":"273","author":"V\u00e9lu, Jacques","year":"1971","journal-title":"C. R. Acad. Sci. Paris S\\'{e}r. A-B","ISSN":"https:\/\/id.crossref.org\/issn\/0151-0509","issn-type":"print"},{"issue":"3","key":"26","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1007\/BF01272074","article-title":"Computing Frobenius maps and factoring polynomials","volume":"2","author":"von zur Gathen, Joachim","year":"1992","journal-title":"Comput. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/1016-3328","issn-type":"print"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2013-82-281\/S0025-5718-2012-02622-6\/S0025-5718-2012-02622-6.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2013-82-281\/S0025-5718-2012-02622-6\/S0025-5718-2012-02622-6.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T17:25:55Z","timestamp":1776792355000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2013-82-281\/S0025-5718-2012-02622-6\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,7,24]]},"references-count":26,"journal-issue":{"issue":"281","published-print":{"date-parts":[[2013,1]]}},"alternative-id":["S0025-5718-2012-02622-6"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-2012-02622-6","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":[[2012,7,24]]}}}