Paper 2004/189

Computing Modular Polynomials

Denis Charles and Kristin Lauter

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.

Note: Small improvements have been made, running times without fast multiplication have been added, and an appendix correcting the run-time analysis of Elkies' method has been added.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. to appear in London Math Society Journal of Computation and Mathematics
Keywords
elliptic curve cryptosystemsnumber theory
Contact author(s)
klauter @ microsoft com
History
2005-06-15: revised
2004-08-07: received
See all versions
Short URL
https://ia.cr/2004/189
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2004/189,
      author = {Denis Charles and Kristin Lauter},
      title = {Computing Modular Polynomials},
      howpublished = {Cryptology ePrint Archive, Paper 2004/189},
      year = {2004},
      note = {\url{https://eprint.iacr.org/2004/189}},
      url = {https://eprint.iacr.org/2004/189}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.