Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Modular polynomials via isogeny volcanoes

Authors: Reinier Bröker, Kristin Lauter and Andrew V. Sutherland
Journal: Math. Comp. 81 (2012), 1201-1231
MSC (2010): Primary 11Y16; Secondary 11G15, 11G20, 14H52
Published electronically: July 14, 2011
MathSciNet review: 2869057
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We present a new algorithm to compute the classical modular polynomial $\Phi _l$ in the rings $\mathbf {Z}[X,Y]$ and $(\mathbf {Z}/m\mathbf {Z})[X,Y]$, for a prime $l$ and any positive integer $m$. Our approach uses the graph of $l$-isogenies to efficiently compute $\Phi _l\bmod p$ for many primes $p$ of a suitable form, and then applies the Chinese Remainder Theorem (CRT). Under the Generalized Riemann Hypothesis (GRH), we achieve an expected running time of $O(l^3 (\log l)^3\log \log l)$, and compute $\Phi _l\bmod m$ using $O(l^2(\log l)^2+ l^2\log m)$ space. We have used the new algorithm to compute $\Phi _l$ with $l$ over 5000, and $\Phi _l\bmod m$ with $l$ over 20000. We also consider several modular functions $g$ for which $\Phi _l^g$ is smaller than $\Phi _l$, allowing us to handle $l$ over 60000.

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


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11Y16, 11G15, 11G20, 14H52

Retrieve articles in all journals with MSC (2010): 11Y16, 11G15, 11G20, 14H52

Additional Information

Reinier Bröker
Affiliation: Brown University, Box 1917, 151 Thayer Street, Providence, Rhode Island 02192
MR Author ID: 759393

Kristin Lauter
Affiliation: Microsoft Research, One Microsoft Way, Redmond, Washington 98052
MR Author ID: 619019
ORCID: 0000-0002-1320-696X

Andrew V. Sutherland
Affiliation: Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
MR Author ID: 852273
ORCID: 0000-0001-7739-2792

Received by editor(s): January 12, 2010
Received by editor(s) in revised form: November 21, 2010
Published electronically: July 14, 2011
Article copyright: © Copyright 2011 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.