Modular polynomials via isogeny volcanoes

Source abstract

We present a new algorithm to compute the classical modular polynomial Φ l \Phi _l in the rings Z [ X , Y ] \mathbf {Z}[X,Y] and ( Z / m Z ) [ X , Y ] (\mathbf {Z}/m\mathbf {Z})[X,Y] , for a prime l l and any positive integer m m . Our approach uses the graph of l l -isogenies to efficiently compute Φ l mod p \Phi _l\bmod p for many primes p 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 ) O(l^3 (\log l)^3\log \log l) , and compute Φ l mod m \Phi _l\bmod m using O ( l 2 ( log ⁡ l ) 2 + l 2 log ⁡ m ) O(l^2(\log l)^2+ l^2\log m) space. We have used the new algorithm to compute Φ l \Phi _l with l l over 5000, and Φ l mod m \Phi _l\bmod m with l l over 20000. We also consider several modular functions g g for which Φ l g \Phi _l^g is smaller than Φ l \Phi _l , allowing us to handle l l over 60000.