Computing isogeny volcanoes of composite degree

DOI10.1016/J.AMC.2011.11.008MaRDI QIDQ426552zbMATH OpenOpenAlexFDO

Authors Dustin Moody

Publication date 11 June 2012

Published in Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.amc.2011.11.008

zbMATH Keywords

cordilleraelliptic curvesisogeniesisogeny volcanoes

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Applications of graph theory (05C90) Curves over finite and local fields (11G20) Number-theoretic algorithms; complexity (11Y16) Isogeny (14K02) Computational aspects of algebraic curves (14Q05)

Review text

Let \(p,\ell\) be two different prime numbers. The set of isomorphism classes of ordinary elliptic curves defined over \(\mathbb{F}_p\), whose \(j\)-invariant is different from \(0\) and \(1728\), can be given the structure of a graph by drawing an edge between every two curves admitting an \(\ell\)-isogeny between them. This graph is called an \(\ell\)-cordillera and its connected components are called volcanoes of \(\ell\)-isogenies. These volcanoes were originally used by \textit{D. Kohel} [Endomorphism rings of elliptic curves over finite fields. PhD thesis, University of California, Berkeley (1996)] to determine the endomorphism ring of an elliptic curve over \(\mathbb{F}_p\) and by \textit{M. Fouquet} and \textit{F. Morain} [Algorithmic number theory. ANTS-V, Lect. Notes Comput. Sci. 2369, 276--291 (2002; Zbl 1058.11041)] to accelerate the SEA algorithm. In this paper it is shown how to speed up the computation of a cordillera once a cordillera of a different degree is known. This is used to compute volcanoes of composite degree more efficiently than a direct construction using modular polynomials.

Recommendations

• scientific article; zbMATH DE number 2086892
• Pairing the volcano
• An algorithm to compute volcanoes of 2-isogenies of elliptic curves over finite fields
• A subexponential algorithm for evaluating large degree isogenies
• Computing endomorphism rings of supersingular elliptic curves and connections to path-finding in isogeny graphs
• Pairing the volcano
• Fast algorithms for computing isogenies between elliptic curves
• Computing the height of volcanoes of -isogenies of elliptic curves over finite fields
• scientific article; zbMATH DE number 1860727
• Isogeny volcanoes of elliptic curves and Sylow subgroups

Cites work

• An algorithm to compute volcanoes of 2-isogenies of elliptic curves over finite fields
• Computing Hilbert class polynomials with the Chinese remainder theorem
• Computing the endomorphism ring of an ordinary elliptic curve over a finite field
• Computing the height of volcanoes of -isogenies of elliptic curves over finite fields
• Constructing Isogenies between Elliptic Curves Over Finite Fields
• Cryptographic hash functions from expander graphs
• scientific article; zbMATH DE number 45834 (Why is no real title available?)
• scientific article; zbMATH DE number 3995866 (Why is no real title available?)
• scientific article; zbMATH DE number 2086892 (Why is no real title available?)
• scientific article; zbMATH DE number 3356934 (Why is no real title available?)
• On Avoiding ZVP-Attacks Using Isogeny Volcanoes
• Pairing the volcano

Cited in

(9)

• Distorting the volcano
• Computing the height of volcanoes of -isogenies of elliptic curves over finite fields
• An algorithm to compute volcanoes of 2-isogenies of elliptic curves over finite fields
• Isogeny volcanoes
• scientific article; zbMATH DE number 2086892 (Why is no real title available?)
• Pairing the volcano
• Pairing the volcano
• Computing modular polynomials and isogenies of rank two Drinfeld modules over finite fields
• Improved supersingularity testing of elliptic curves using Legendre form

This page was built for publication: Computing isogeny volcanoes of composite degree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q426552)