Computing Modular Polynomials

DOI10.1112/S1461157000000954zbMATH Open1119.11030arXivmath/0408051MaRDI QIDQ5697474FDOQ5697474

Authors: Denis Xavier Charles, Kristin Lauter 

Publication date: 17 October 2005

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

Abstract: We present a new probabilistic algorithm to compute modular polynomials modulo a prime. Modular polynomials parameterize pairs of isogenous elliptic curves and are useful in many aspects of computational number theory and cryptography. Our algorithm has the distinguishing feature that it does not involve the computation of Fourier coefficients of modular forms. We avoid computing the exponentially large integral coefficients by working directly modulo a prime and computing isogenies between elliptic curves via Velu's formulas.

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

Recommendations

• Modular polynomials via isogeny volcanoes
• Computing modular polynomials in quasi-linear time
• On the evaluation of modular polynomials
• Hilbert modular polynomials
• Modular Polynomials for Genus 2

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Applications to coding theory and cryptography of arithmetic geometry (14G50) Arithmetic aspects of modular and Shimura varieties (11G18) Elliptic curves (14H52)

Cites Work

• Über die Entwicklungskoeffizienten der automorphen Formen
• The least quadratic non residue
• Nonsingular plane cubic curves over finite fields
• Fast construction of irreducible polynomials over finite fields
• On Character Sums and Primitive Roots^†
• On the coefficients of the transformation polynomials for the elliptic modular function
• On the coefficients of transformation polynomials for the modular function

Cited In (28)

• Modular polynomials via isogeny volcanoes
• On some probabilistic aspects around modular methods
• On the computation of the modular equation
• Two remarks on the modular polynomial of \(j(z)\)
• Some properties of reduced modular polynomials
• Title not available (Why is that?)
• Approximate computations with modular curves
• A quasi-linear time algorithm for computing modular polynomials in dimension 2
• Better path-finding algorithms in LPS Ramanujan graphs
• Computing modular polynomials in quasi-linear time
• Modular polynomials on Hilbert surfaces
• Learning read-constant polynomials of constant degree modulo composites
• Computing modular polynomials and isogenies of rank two Drinfeld modules over finite fields
• Cryptographic hash functions from expander graphs
• Computing the permanent modulo a prime power
• Learning Read-Constant Polynomials of Constant Degree Modulo Composites
• Modular polynomials
• An explicit height bound for the classical modular polynomial
• Computing coefficients of modular forms
• Hilbert modular polynomials
• Fast algorithms for computing isogenies between elliptic curves
• Computing modular polynomials by deformation
• Title not available (Why is that?)
• Factoring modular polynomials
• On explicit formulas for the modular equation
• On Avoiding ZVP-Attacks Using Isogeny Volcanoes
• On the evaluation of modular polynomials
• Computing the characteristic polynomial of a finite rank two Drinfeld module

This page was built for publication: Computing Modular Polynomials

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