Computing modular polynomials in quasi-linear time

DOI10.1090/S0025-5718-09-02199-1zbMath1215.11121MaRDI QIDQ3055173

Andreas Enge

Publication date: 7 November 2010

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

zbMATH Keywords

modular functionsmodular groupmodular polynomialsSchläfli equations

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Complex multiplication and moduli of abelian varieties (11G15) Heights (11G50)

Related Items

A quasi-linear time algorithm for computing modular polynomials in dimension 2 ⋮ Hilbert modular polynomials ⋮ Computational Number Theory, Past, Present, and Future ⋮ Class polynomials for nonholomorphic modular functions ⋮ Certified Newton schemes for the evaluation of low-genus theta functions ⋮ Computing the endomorphism ring of an ordinary elliptic curve over a finite field ⋮ Modular polynomials via isogeny volcanoes ⋮ Choosing the correct elliptic curve in the CM method ⋮ A Subexponential Algorithm for Evaluating Large Degree Isogenies ⋮ An explicit height bound for the classical modular polynomial ⋮ Computing Hilbert class polynomials with the Chinese remainder theorem ⋮ Expander graphs based on GRH with an application to elliptic curve cryptography ⋮ On Elkies subgroups of \(\ell\)-torsion points in elliptic curves defined over a finite field ⋮ Short addition sequences for theta functions ⋮ 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

Uses Software

• gmp
• MPFR
• MPC

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computing the number of points on an elliptic curve over a finite field: algorithmic aspects
• Constructing elliptic curves over finite fields using double eta-quotients
• Fast multiplication of large numbers
• Fast evaluation of modular functions using Newton iterations and the AGM
• The complexity of class polynomial computation via floating point approximations
• On the coefficients of the transformation polynomials for the elliptic modular function
• Constructing elliptic curves of prime order
• MPFR
• Constructing Isogenies between Elliptic Curves Over Finite Fields
• Modular curves of composite level
• Computing Modular Polynomials
• Hyperelliptic modular curves