Computing Modular Polynomials

DOI10.1112/S1461157000000954MaRDI QIDQ5697474zbMATH OpenFDO

Authors Denis Xavier Charles, Kristin Lauter

Publication date 17 October 2005

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

Full work available at URL https://arxiv.org/abs/math/0408051, http://www.lms.ac.uk/jcm/8/lms2005-006/

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)

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.

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

Cites work

• Fast construction of irreducible polynomials over finite fields
• Nonsingular plane cubic curves 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
• The least quadratic non residue
• Über die Entwicklungskoeffizienten der automorphen Formen

Cited in

(28)

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

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)