International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Computing Modular Polynomials

Denis Charles
Kristin Lauter
Search ePrint
Search Google
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.
  title={Computing Modular Polynomials},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / elliptic curve cryptosystems, number theory},
  note={to appear in London Math Society Journal of Computation and Mathematics 12949 received 3 Aug 2004, last revised 15 Jun 2005},
  author={Denis Charles and Kristin Lauter},