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

DOI10.1112/S1461157015000170MaRDI QIDQ3196365zbMATH OpenFDO

Authors Enea Milio

Publication date 29 October 2015

Published in LMS Journal of Computation and Mathematics (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Siegel modular groups; Siegel and Hilbert-Siegel modular and automorphic forms (11F46) Analytic computations (11Y35)

Abstract: We propose to generalize the work of R'egis 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.

Recommendations

• Computing modular polynomials in quasi-linear time
• Modular polynomials on Hilbert surfaces
• Modular Polynomials for Genus 2
• Computing Modular Polynomials
• Modular polynomials via isogeny volcanoes

Cites work

• Arithmetic variety of moduli for genus two
• Class invariants by the CRT method
• Computing class polynomials for abelian surfaces
• Computing Hilbert Class Polynomials
• Computing Hilbert class polynomials with the Chinese remainder theorem
• Computing modular polynomials in quasi-linear time
• Computing the endomorphism ring of an ordinary elliptic curve over a finite field
• Constructing hyperelliptic curves of genus 2 suitable for cryptography
• Counting points on elliptic curves over finite fields
• Endomorphism rings of abelian surfaces and projective models of their moduli spaces
• Explizite Bestimmung der Randflächen des Fundamentalbereiches der Modulgruppe zweiten Grades
• Fast evaluation of holonomic functions
• Fast multiplication of large numbers
• scientific article; zbMATH DE number 3854294 (Why is no real title available?)
• Modular Polynomials for Genus 2
• Modular polynomials via isogeny volcanoes
• Modular Varieties with Level 2 Theta Structure
• On Siegel Modular Forms of Genus Two
• Tata lectures on theta. I: Introduction and motivation: Theta functions in one variable. Basic results on theta functions in several variables. With the assistance of C. Musili, M. Nori, E. Previato, and M. Stillman
• Tata lectures on theta. II: Jacobian theta functions and differential equations. With the collaboration of C. Musili, M. Nori, E. Previato, M. Stillman, and H. Umemura

Cited in

(13)

• Computing invariants of the Weil representation
• Computing models for quotients of modular curves
• Computing the 2-adic canonical lift of genus 2 curves
• Hilbert modular polynomials
• Constructing Polynomials for Functions over Residue Rings Modulo a Composite Number in Linear Time
• Computing theta functions in quasi-linear time in genus two and above
• Computing modular polynomials in quasi-linear time
• Cyclic isogenies for abelian varieties with real multiplication
• scientific article; zbMATH DE number 7659953 (Why is no real title available?)
• Degree and height estimates for modular equations on PEL Shimura varieties
• Computing modular polynomials by deformation
• Computing isogenies from modular equations in genus two
• Modular polynomials on Hilbert surfaces

This page was built for publication: A quasi-linear time algorithm for computing modular polynomials in dimension 2

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