A quasi-linear time algorithm for computing modular polynomials in dimension 2

Abstract

We propose to generalize the work of Régis Dupont for computing modular polynomials in dimension $2$ to new invariants. We describe an algorithm to compute modular polynomials for invariants derived from theta constants and prove under some heuristics that this algorithm is quasi-linear in its output size. Some properties of the modular polynomials defined from quotients of theta constants are analyzed. We report on experiments with our implementation.

Cited by in corpus (5)

• Sign choices in the AGM for genus two theta constants
• Degree and height estimates for modular equations on PEL Shimura varieties
• Computing isogenies from modular equations in genus two
• Isogenies for point counting on genus two hyperelliptic curves with maximal real multiplication
• Evaluating modular equations for abelian surfaces