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
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
(29)- Computing the characteristic polynomial of a finite rank two Drinfeld module
- Modular polynomials via isogeny volcanoes
- On the computation of the modular equation
- On some probabilistic aspects around modular methods
- Two remarks on the modular polynomial of j(z)
- Some properties of reduced modular polynomials
- scientific article; zbMATH DE number 1057052 (Why is no real title available?)
- Better path-finding algorithms in LPS Ramanujan graphs
- A quasi-linear time algorithm for computing modular polynomials in dimension 2
- Approximate computations with modular curves
- 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
- An explicit height bound for the classical modular polynomial
- Modular polynomials
- Congruence properties of the coefficients of the classical modular polynomials
- Computing coefficients of modular forms
- Hilbert modular polynomials
- Fast algorithms for computing isogenies between elliptic curves
- Computing modular polynomials by deformation
- scientific article; zbMATH DE number 2092278 (Why is no real title available?)
- Factoring modular polynomials
- On explicit formulas for the modular equation
- On Avoiding ZVP-Attacks Using Isogeny Volcanoes
- On the evaluation of modular polynomials
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)
