Mathematics – Number Theory
Scientific paper
2010-09-06
Mathematics
Number Theory
significant revision with several new lemmas and propositions, 36 pages
Scientific paper
Given a prime q and a negative discriminant D, the CM method constructs an elliptic curve E/\Fq by obtaining a root of the Hilbert class polynomial H_D(X) modulo q. We consider an approach based on a decomposition of the ring class field defined by H_D, which we adapt to a CRT setting. This yields two algorithms, each of which obtains a root of H_D mod q without necessarily computing any of its coefficients. Heuristically, our approach uses asymptotically less time and space than the standard CM method for almost all D. Under the GRH, and reasonable assumptions about the size of log q relative to |D|, we achieve a space complexity of O((m+n)\log q) bits, where mn=h(D), which may be as small as O(|D|^(1/4)log q). The practical efficiency of the algorithms is demonstrated using |D| > 10^16 and q ~ 2^256, and also |D| > 10^15 and q ~ 2^33220. These examples are both an order of magnitude larger than the best previous results obtained with the CM method.
No associations
LandOfFree
Accelerating the CM method 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 Accelerating the CM method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Accelerating the CM method will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-298576