Cryptology ePrint Archive: Report 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.
Category / Keywords: public-key cryptography / elliptic curve cryptosystems, number theory
Publication Info: to appear in London Math Society Journal of Computation and Mathematics
Date: received 3 Aug 2004, last revised 15 Jun 2005
Contact author: klauter at microsoft com
Available format(s): PDF | BibTeX Citation
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.
Version: 20050615:221450 (All versions of this report)
Short URL: ia.cr/2004/189
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]