Computing modular polynomials
Denis Charles and Kristin Lauter
Abstract: This paper presents 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. The
algorithm presented here has the distinguishing feature that it
does not involve the computation of Fourier coefficients of
modular forms. The need to compute the exponentially large
integral coefficients is avoided by working directly modulo a
prime, and computing isogenies between elliptic curves via
Vélu's formulas.
|
