Please use this identifier to cite or link to this item:
DC FieldValueLanguage
dc.contributor.authorSutherland, Andrew Ven_US
dc.identifier.citationLms Journal of Computation and Mathematics 2012 vol: 15 pp: 172-204en_US
dc.description.abstractGiven 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 HD(X) modulo q. We consider an approach based on a decomposition of the ring class field defined by HD, which we adapt to a CRT setting. This yields two algorithms, each of which obtains a root of HD 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| > 1016 and q ≈ 2 256, and also |D| > 1015 and q ≈ 2 33220. These examples are both an order of magnitude larger than the best previous results obtained with the CM method.en_US
dc.publisherLMS Journal of Computation and Mathematicsen_US
dc.subjectCM methoden_US
dc.subjectPrime qen_US
dc.subjectHilbert class polynomial HD(X)en_US
dc.titleAccelerating the CM methoden_US
Appears in Collections:Eng - Journal articles (DHET subsidised)
Show simple item record

Page view(s)

Last Week
Last month
checked on Feb 9, 2021

Google ScholarTM


This item is licensed under a Creative Commons License Creative Commons