Accelerating the CM method

作者：Sutherland Andrew V^*

来源：LMS Journal of Computation and Mathematics, 2012, 15: 172-204.

DOI：10.1112/S1461157012001015

Given a prime q and a negative discriminant D, the CM method constructs an elliptic curve E=F-q 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 vertical bar D vertical bar, we achieve a space complexity of O((m + n) log q) bits, where mn = h(D), which may be as small as O(vertical bar D vertical bar(1/4) log q). The practical efficiency of the algorithms is demonstrated using vertical bar D vertical bar > 10(16) and q approximate to 2(256), and also vertical bar D vertical bar > 10(15) and q approximate to 2(33220). These examples are both an order of magnitude larger than the best previous results obtained with the CM method.

• 出版日期2012