Modular polynomials via isogeny volcanoes

Abstract

We present a new algorithm to compute the classical modular polynomial Phi_n in the rings Z[X,Y] and (Z/mZ)[X,Y], for a prime n and any positive integer m. Our approach uses the graph of n-isogenies to efficiently compute Phi_n mod p for many primes p of a suitable form, and then applies the Chinese Remainder Theorem (CRT). Under the Generalized Riemann Hypothesis (GRH), we achieve an expected running time of O(n^3 (log n)^3 log log n), and compute Phi_n mod m using O(n^2 (log n)^2 + n^2 log m) space. We have used the new algorithm to compute Phi_n with n over 5000, and Phi_n mod m with n over 20000. We also consider several modular functions g for which Phi_n^g is smaller than Phi_n, allowing us to handle n over 60000.

corrected a typo in equation (14), 31 pages

Cited by in corpus (20)

• Isogeny volcanoes
• Computing images of Galois representations attached to elliptic curves
• Class polynomials for nonholomorphic modular functions
• Accelerating the CM method
• $\ell$-adic images of Galois for elliptic curves over $\mathbb{Q}$
• On the distribution of Atkin and Elkies primes for reductions of elliptic curves on average
• A Subexponential Algorithm for Evaluating Large Degree Isogenies
• A quasi-linear time algorithm for computing modular polynomials in dimension 2
• On the evaluation of modular polynomials
• Computing separable isogenies in quasi-optimal time
• Cuts and Isogenies
• Flux Vacua and Modularity for ${\mathbb{Z}}_2$ Symmetric Calabi-Yau Manifolds
• Sato-Tate distributions of twists of the Fermat and the Klein quartics
• Explicit isogenies in quadratic time in any characteristic
• On the Distribution of Atkin and Elkies Primes
• Generalized class group actions on oriented elliptic curves with level structure
• Explicit classification of isogeny graphs of rational elliptic curves
• Iwasawa Invariants for elliptic curves over ${\mathbb{Z}}_p$-extensions and Kida's Formula
• Computing supersingular endomorphism rings using inseparable endomorphisms
• Computing the endomorphism ring of an elliptic curve over a number field