Accelerating the CM method

Abstract

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.

36 pages, minor edits, to appear in the LMS Journal of Computation and Mathematics

References in corpus (6)

• Computing the endomorphism ring of an ordinary elliptic curve over a finite field
• Computing Hilbert class polynomials with the Chinese Remainder Theorem
• Modular polynomials via isogeny volcanoes
• Class invariants by the CRT method
• Algorithms for Finding Almost Irreducible and Almost Primitive Trinomials
• Structure computation and discrete logarithms in finite abelian p-groups

Cited by in corpus (10)

• Isogeny volcanoes
• Computing classical modular forms
• On the evaluation of modular polynomials
• Genus-2 curves and Jacobians with a given number of points
• An explicit version of Shimura's reciprocity law for Siegel modular functions
• Constructing Picard curves with complex multiplication using the Chinese Remainder Theorem
• Cycles of supersingular elliptic curves for pairing-based proof systems
• Finding elliptic curves with a subgroup of prescribed size
• Pre- and post-quantum Diffie-Hellman from groups, actions, and isogenies
• Hard isogeny problems over RSA moduli and groups with infeasible inversion