Modular polynomials via isogeny volcanoes

Details Modular polynomials via isogeny volcanoes Modular polynomials via isogeny volcanoes

2010-01-03

arxiv.org/abs/1001.0402v2

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.

Affiliated with

Also associated with

No associations

Rating

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.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-223005