Computing Modular Polynomials

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

Kristin Lauter, Denis Xavier Charles

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

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 (20)

• Modular polynomials via isogeny volcanoes
• On the computation of the modular equation
• Computing modular polynomials and isogenies of rank two Drinfeld modules over finite fields
• Two remarks on the modular polynomial of \(j(z)\)
• Some properties of reduced modular polynomials
• Title not available (Why is that?)
• Better path-finding algorithms in LPS Ramanujan graphs
• Computing modular polynomials in quasi-linear time
• Learning read-constant polynomials of constant degree modulo composites
• Cryptographic hash functions from expander graphs
• Computing the permanent modulo a prime power
• Learning Read-Constant Polynomials of Constant Degree Modulo Composites
• An explicit height bound for the classical modular polynomial
• Computing coefficients of modular forms
• Fast algorithms for computing isogenies between elliptic curves
• 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

   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 👍 👎

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)