@article{broker2012modular,
author = {Broker, Reinier and Lauter, Kristin and Sutherland, Andrew V.},
title = {Modular polynomials via isogeny volcanoes},
year = {2012},
month = {January},
abstract = {We present a new algorithm to compute the classical modular polynomial Phi_n in the rings Z[X,Y] and (Z/mZ)[X,Y], for a prime n and any positive integer m. Our approach uses the graph of n-isogenies to efficiently compute Phi_n mod 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(n^3 (log n)^3 log log n), and compute Phi_n mod m using O(n^2 (log n)^2 + n^2 log m) space. We have used the new algorithm to compute Phi_n with n over 5000, and Phi_n mod m with n over 20000. We also consider several modular functions g for which Phi_n^g is smaller than Phi_n, allowing us to handle n over 60000.},
publisher = {American Mathematical Society},
url = {http://approjects.co.za/?big=en-us/research/publication/modular-polynomials-via-isogeny-volcanoes/},
journal = {Mathematics of Computation 81 (2012), 1201-1231},
volume = {81},
edition = {Mathematics of Computation},
}