Modular polynomials via isogeny volcanoes

DOI10.1090/S0025-5718-2011-02508-1zbMath1267.11125arXiv1001.0402MaRDI QIDQ5389453

Andrew V. Sutherland, Reinier Bröker, Kristin E. Lauter

Publication date: 26 April 2012

Published in: Mathematics of Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1001.0402

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Curves over finite and local fields (11G20) Complex multiplication and moduli of abelian varieties (11G15)

Related Items (41)

Automorphisms and isogeny graphs of abelian varieties, with applications to the superspecial Richelot isogeny graph ⋮ Explicit classification of isogeny graphs of rational elliptic curves ⋮ On isogeny graphs of supersingular elliptic curves over finite fields ⋮ Quantum lattice enumeration and tweaking discrete pruning ⋮ Constructing Permutation Rational Functions from Isogenies ⋮ Iwasawa invariants for elliptic curves over \(\mathbb{Z}_p\)-extensions and Kida's formula ⋮ A quasi-linear time algorithm for computing modular polynomials in dimension 2 ⋮ On a simple model of \(X_0(N)\) ⋮ On the Security of OSIDH ⋮ Isolated elliptic curves and the MOV attack ⋮ Distorting the volcano ⋮ -adic images of Galois for elliptic curves over (and an appendix with John Voight) ⋮ Hilbert's irreducibility, modular forms, and computation of certain Galois groups ⋮ Hyperelliptic Integrals to Elliptic Integrals ⋮ On the distribution of Atkin and Elkies primes ⋮ Class polynomials for nonholomorphic modular functions ⋮ Computing the endomorphism ring of an ordinary elliptic curve over a finite field ⋮ Explicit isogenies in quadratic time in any characteristic ⋮ Fast heuristic algorithms for computing relations in the class group of a quadratic order, with applications to isogeny evaluation ⋮ Towards practical key exchange from ordinary isogeny graphs ⋮ Hecke stability and weight 1 modular forms ⋮ \(\mathbb{Q}\)-curves over odd degree number fields ⋮ Isogeny graphs of ordinary abelian varieties ⋮ New examples of maximal curves with low genus ⋮ On degrees and birationality of the maps \(X_0(N)\to \mathbb P^2\) constructed via modular forms ⋮ Accelerating the CM method ⋮ Computing separable isogenies in quasi-optimal time ⋮ Elliptic curves over \(\mathbb {Q}\) and 2-adic images of Galois ⋮ A Subexponential Algorithm for Evaluating Large Degree Isogenies ⋮ Computations with Witt vectors of length 3 ⋮ An explicit height bound for the classical modular polynomial ⋮ Analogues of Vélu’s formulas for isogenies on alternate models of elliptic curves ⋮ On primitive elements of algebraic function fields and models of \(X_0(N)\) ⋮ Cuts and isogenies ⋮ Sato-Tate distributions of twists of the Fermat and the Klein quartics ⋮ Modular forms constructed from moduli of elliptic curves, with applications to explicit models of modular curves ⋮ Computing modular polynomials and isogenies of rank two Drinfeld modules over finite fields ⋮ Modular polynomials on Hilbert surfaces ⋮ Computing $(\ell ,\ell )$-isogenies in polynomial time on Jacobians of genus $2$ curves ⋮ On the distribution of Atkin and Elkies primes for reductions of elliptic curves on average ⋮ Generalized class polynomials

Uses Software

• gmp
• Magma
• SageMath
• zn_poly

Cites Work

• Faster polynomial multiplication via multipoint Kronecker substitution
• Binary quadratic forms. An algorithmic approach
• An explicit height bound for the classical modular polynomial
• Computation of the modular equation
• Counting points on elliptic curves over finite fields
• Computing the number of points on an elliptic curve over a finite field: algorithmic aspects
• Computing the endomorphism ring of an ordinary elliptic curve over a finite field
• Constructing elliptic curves over finite fields using double eta-quotients
• Fast multiplication of large numbers
• A $p$-adic algorithm to compute the Hilbert class polynomial
• The complexity of class polynomial computation via floating point approximations
• Computing modular polynomials in quasi-linear time
• Computing Hilbert class polynomials with the Chinese remainder theorem
• On the coefficients of the transformation polynomials for the elliptic modular function
• Modular exponentiation via the explicit Chinese remainder theorem
• Explicit Bounds for Primality Testing and Related Problems
• Constructing elliptic curves of prime order
• Fast algorithms for computing isogenies between elliptic curves
• On the Security of Cryptosystems with Quadratic Decryption: The Nicest Cryptanalysis
• A Rigorous Time Bound for Factoring Integers
• Über die Berechnung der Fourierkoeffizienten der Funktion j().
• Class Invariants by the CRT Method
• Advanced Topics in Computional Number Theory
• Modular curves of composite level
• Handbook of Elliptic and Hyperelliptic Curve Cryptography
• Computing Hilbert Class Polynomials
• Factoring Polynomials Over Large Finite Fields
• Computing Modular Polynomials
• SAGE
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Modular polynomials via isogeny volcanoes