Modular polynomials via isogeny volcanoes

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.