Modular polynomials via isogeny volcanoes

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.