## Pairing the volcano

HTML articles powered by AMS MathViewer

- by Sorina Ionica and Antoine Joux PDF
- Math. Comp.
**82**(2013), 581-603 Request permission

## Abstract:

Isogeny volcanoes are graphs whose vertices are elliptic curves and whose edges are $\ell$-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’s and Fouquet-Morain’s 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 $P$ of order $\ell$ such that the subgroup generated by $P$ 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’s method for computing the $\ell$-adic valuation of the conductor of the endomorphism ring for small $\ell$.## References

- Juliana Belding, Reinier Bröker, Andreas Enge, and Kristin Lauter,
*Computing Hilbert class polynomials*, Algorithmic number theory, Lecture Notes in Comput. Sci., vol. 5011, Springer, Berlin, 2008, pp. 282–295. MR**2467854**, DOI 10.1007/978-3-540-79456-1_{1}9 - Gaetan Bisson and Andrew V. Sutherland,
*Computing the endomorphism ring of an ordinary elliptic curve over a finite field*, J. Number Theory**131**(2011), no. 5, 815–831. MR**2772473**, DOI 10.1016/j.jnt.2009.11.003 - R. Broker, K. Lauter, and A. Sutherland. Computing modular polynomials with the chinese remainder theorem. http://arxiv.org/abs/1001.0402, 2009.
- D. Charles. On the existence of distortion maps on ordinary curves. http://eprint.iacr.org/2006/128.
- David A. Cox,
*Primes of the form $x^2 + ny^2$*, A Wiley-Interscience Publication, John Wiley & Sons, Inc., New York, 1989. Fermat, class field theory and complex multiplication. MR**1028322** - Max Deuring,
*Die Typen der Multiplikatorenringe elliptischer Funktionenkörper*, Abh. Math. Sem. Hansischen Univ.**14**(1941), 197–272 (German). MR**5125**, DOI 10.1007/BF02940746 - M. Fouquet.
*Anneau d’endomorphismes et cardinalité des courbes elliptiques: aspects algorithmiques*. PhD thesis, Ecole Polytechnique, 2001. - 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 - Gerhard Frey,
*Applications of arithmetical geometry to cryptographic constructions*, Finite fields and applications (Augsburg, 1999) Springer, Berlin, 2001, pp. 128–161. MR**1849086** - P. Grabher, J. Großschädl, 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–50. Springer, 2009. - Sorina Ionica and Antoine Joux,
*Pairing the volcano*, Algorithmic number theory, Lecture Notes in Comput. Sci., vol. 6197, Springer, Berlin, 2010, pp. 201–208. MR**2721422**, DOI 10.1007/978-3-642-14518-6_{1}8 - Antoine Joux and Kim Nguyen,
*Separating decision Diffie-Hellmann from computational Diffie-Hellman in cryptographic groups*, J. Cryptology**16**(2003), no. 4, 239–247. MR**2002044**, DOI 10.1007/s00145-003-0052-4 - H. W. Lenstra Jr.,
*Complex multiplication structure of elliptic curves*, J. Number Theory**56**(1996), no. 2, 227–241. MR**1373549**, DOI 10.1006/jnth.1996.0015 - David Russell Kohel,
*Endomorphism rings of elliptic curves over finite fields*, ProQuest LLC, Ann Arbor, MI, 1996. Thesis (Ph.D.)–University of California, Berkeley. MR**2695524** - David Freeman and Kristin Lauter,
*Computing endomorphism rings of Jacobians of genus 2 curves over finite fields*, Algebraic geometry and its applications, Ser. Number Theory Appl., vol. 5, World Sci. Publ., Hackensack, NJ, 2008, pp. 29–66. MR**2484047**, DOI 10.1142/9789812793430_{0}002 - Victor S. Miller,
*The Weil pairing, and its efficient calculation*, J. Cryptology**17**(2004), no. 4, 235–261. MR**2090556**, DOI 10.1007/s00145-004-0315-8 - J. Miret, R. Moreno, D. Sadornil, J. Tena, and M. Valls,
*An algorithm to compute volcanoes of 2-isogenies of elliptic curves over finite fields*, Appl. Math. Comput.**176**(2006), no. 2, 739–750. MR**2232066**, DOI 10.1016/j.amc.2005.10.020 - J. Miret, R. Moreno, D. Sadornil, J. Tena, and M. Valls,
*Computing the height of volcanoes of $l$-isogenies of elliptic curves over finite fields*, Appl. Math. Comput.**196**(2008), no. 1, 67–76. MR**2382590**, DOI 10.1016/j.amc.2007.05.037 - Peter Lawrence Montgomery,
*An FFT extension of the elliptic curve method of factorization*, ProQuest LLC, Ann Arbor, MI, 1992. Thesis (Ph.D.)–University of California, Los Angeles. MR**2688742** - Hans-Georg Rück,
*A note on elliptic curves over finite fields*, Math. Comp.**49**(1987), no. 179, 301–304. MR**890272**, DOI 10.1090/S0025-5718-1987-0890272-3 - 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** - 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 - Andrew V. Sutherland,
*Computing Hilbert class polynomials with the Chinese remainder theorem*, Math. Comp.**80**(2011), no. 273, 501–538. MR**2728992**, DOI 10.1090/S0025-5718-2010-02373-7 - Jacques Vélu,
*Isogénies entre courbes elliptiques*, C. R. Acad. Sci. Paris Sér. A-B**273**(1971), A238–A241 (French). MR**294345** - Joachim von zur Gathen and Victor Shoup,
*Computing Frobenius maps and factoring polynomials*, Comput. Complexity**2**(1992), no. 3, 187–224. MR**1220071**, DOI 10.1007/BF01272074

## Additional Information

**Sorina Ionica**- Affiliation: Laboratoire d’Informatique de l’Ecole Polytechnique (LIX) 91128 Palaiseau CEDEX, France
- Address at time of publication: LORIA (UMR 7503), Equipe-projet CARAMEL, Bâtiment A, Campus Scientifique – BP 239, 54506 Vandœuvre-lès-Nancy Cedex, France
- Email: sorina.ionica@gmail.com
**Antoine Joux**- Affiliation: DGA and Université de Versailles Saint-Quentin-en-Yvelines, 45 avenue des États-Unis, 78035 Versailles CEDEX, France
- MR Author ID: 316495
- Email: antoine.joux@m4x.org
- Received by editor(s): November 16, 2010
- Received by editor(s) in revised form: August 30, 2011
- Published electronically: July 24, 2012
- Additional Notes: This work has been carried out at Prism Laboratory, University of Versailles and is part of the author’s PhD thesis.
- © Copyright 2012
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication. - Journal: Math. Comp.
**82**(2013), 581-603 - MSC (2010): Primary 14H52; Secondary 14K02
- DOI: https://doi.org/10.1090/S0025-5718-2012-02622-6
- MathSciNet review: 2983037