Mathematics – Number Theory
Scientific paper
2010-01-03
Math. Comp. 81 (2012), 1201-1231
Mathematics
Number Theory
corrected a typo in equation (14), 31 pages
Scientific paper
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.
Broker Reinier
Lauter Kristin
Sutherland Andrew V.
No associations
LandOfFree
Modular polynomials via isogeny volcanoes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Modular polynomials via isogeny volcanoes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Modular polynomials via isogeny volcanoes will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-223005