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

Arithmetic aspects of modular and Shimura varieties (11G18) Number-theoretic algorithms; complexity (11Y16) Applications to coding theory and cryptography of arithmetic geometry (14G50) 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

(30)

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

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)