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

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

Kristin Lauter
Affiliation: Microsoft Research, One Microsoft Way, Redmond, Washington 98052

Andrew V. Sutherland
Affiliation: Massachusetts Institute of Technology, Cambridge, Massachusetts 02139

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.

American Mathematical Society