2004/08/03 by Denis Charles, Kristin Lauter, Charles, Denis +1 · 2 citations
Computer Science · Mathematics · #11G18 #11Y16 #Algebraic Geometry (math.AG) #Algebraic Geometry and Number Theory #Cryptography and Residue Arithmetic #FOS: Mathematics #Number Theory (math.NT) #Polynomial and algebraic computation #math.AG #math.NT #msc:11G18 #msc:11Y16
paper · pdf · doi:10.48550/arxiv.math/0408051
8 pages, appendix added with correction to Elkies' running time, final version to appear in London Math Society Journal of Computation and Mathematics
openalex publication_date 2004/08/03 · arxiv created 2005/07/07 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.