Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Computing modular polynomials in quasi-linear time

Author: Andreas Enge
Journal: Math. Comp. 78 (2009), 1809-1824
MSC (2000): Primary 11Y16; Secondary 11G15
Published electronically: March 11, 2009
MathSciNet review: 2501077
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information


We analyse and compare the complexity of several algorithms for computing modular polynomials. Under the assumption that rounding errors do not influence the correctness of the result, which appears to be satisfied in practice, we show that an algorithm relying on floating point evaluation of modular functions and on interpolation has a complexity that is up to logarithmic factors linear in the size of the computed polynomials. In particular, it obtains the classical modular polynomial $\Phi _\ell$ of prime level $\ell$ in time \[ O \left (\ell ^2 \log ^3 \ell M (\ell ) \right ) \subseteq O \left ( \ell ^3 \log ^{4 + \varepsilon }\ell \right ), \] where $M(\ell )$ is the time needed to multiply two $\ell$-bit numbers.

Besides treating modular polynomials for $\Gamma ^0 (\ell )$, which are an important ingredient in many algorithms dealing with isogenies of elliptic curves, the algorithm is easily adapted to more general situations. Composite levels are handled just as easily as prime levels, as well as polynomials between a modular function and its transform of prime level, such as the Schläfli polynomials and their generalisations.

Our distributed implementation of the algorithm confirms the theoretical analysis by computing modular equations of record level around $10000$ in less than two weeks on ten processors.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11Y16, 11G15

Retrieve articles in all journals with MSC (2000): 11Y16, 11G15

Additional Information

Andreas Enge
Affiliation: INRIA Saclay–Île-de-France & Laboratoire d’Informatique (CNRS/UMR 7161), École polytechnique, 91128 Palaiseau Cedex, France

Received by editor(s): April 24, 2007
Received by editor(s) in revised form: May 13, 2008
Published electronically: March 11, 2009
Article copyright: © Copyright 2009 Andreas Enge