Sutherland, Andrew V. Accelerating the CM method. (English) Zbl 1343.11098 LMS J. Comput. Math. 15, 172-204 (2012). Summary: Given a prime \(q\) and a negative discriminant \(D\), the CM method constructs an elliptic curve \(E/\mathbb 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 \(|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\approx 2^{256}\), and also \(|D|>10^{15}\) and \(q\approx 2^{33220}\). These examples are both an order of magnitude larger than the best previous results obtained with the CM method. Cited in 13 Documents MSC: 11Y16 Number-theoretic algorithms; complexity 11G15 Complex multiplication and moduli of abelian varieties 11G20 Curves over finite and local fields 14G15 Finite ground fields in algebraic geometry 14H52 Elliptic curves Software:zn_poly PDFBibTeX XMLCite \textit{A. V. Sutherland}, LMS J. Comput. Math. 15, 172--204 (2012; Zbl 1343.11098) Full Text: DOI arXiv References: [1] DOI: 10.1007/BF02242355 · Zbl 0223.68007 · doi:10.1007/BF02242355 [2] Cox, Primes of the form (1989) [3] DOI: 10.1090/S0025-5718-09-02266-2 · Zbl 1213.11127 · doi:10.1090/S0025-5718-09-02266-2 [4] DOI: 10.1090/S0025-5718-1970-0276200-X · doi:10.1090/S0025-5718-1970-0276200-X [5] DOI: 10.1007/978-3-540-79456-1_19 · Zbl 1205.11139 · doi:10.1007/978-3-540-79456-1_19 [6] DOI: 10.1007/BFb0054855 · doi:10.1007/BFb0054855 [7] DOI: 10.1142/S1793042109002523 · Zbl 1221.11197 · doi:10.1142/S1793042109002523 [8] DOI: 10.1112/plms/s2-27.1.358 · JFM 54.0206.02 · doi:10.1112/plms/s2-27.1.358 [9] DOI: 10.1090/S0025-5718-1990-1023756-8 · doi:10.1090/S0025-5718-1990-1023756-8 [10] DOI: 10.1007/978-1-4612-4752-4 · doi:10.1007/978-1-4612-4752-4 [11] Bach, ACM Distinguished Dissertation 1984 (1985) [12] Lagarias, Algebraic number fields: pp 409– (1977) [13] DOI: 10.1090/S0025-5718-1993-1199989-X · doi:10.1090/S0025-5718-1993-1199989-X [14] DOI: 10.1007/978-3-642-14518-6_18 · Zbl 1260.11044 · doi:10.1007/978-3-642-14518-6_18 [15] DOI: 10.4007/annals.2004.160.781 · Zbl 1071.11070 · doi:10.4007/annals.2004.160.781 [16] DOI: 10.1016/j.tcs.2009.03.014 · Zbl 1172.68065 · doi:10.1016/j.tcs.2009.03.014 [17] Agashe, High primes and misdemeanours: lectures in honour of the 60th Birthday of Hugh Cowie Williams pp 1– (2004) · doi:10.1090/fic/041/01 [18] Hardy, An introduction to the theory of numbers (1979) · Zbl 0423.10001 [19] Hanrot, International Conference on Symbolic and Algebraic Computation–ISSAC 2001 pp 175– (2001) [20] Gee, Algorithmic Number Theory Symposium–ANTS III pp 442– (1998) [21] DOI: 10.1007/978-3-642-14518-6_14 · Zbl 1260.11083 · doi:10.1007/978-3-642-14518-6_14 [22] DOI: 10.1007/3-540-44828-4_27 · Zbl 1030.11078 · doi:10.1007/3-540-44828-4_27 [23] DOI: 10.1007/3-540-45455-1_21 · doi:10.1007/3-540-45455-1_21 [24] DOI: 10.1090/S0025-5718-08-02200-X · Zbl 1208.11136 · doi:10.1090/S0025-5718-08-02200-X [25] Crandall, Prime numbers: a computational perspective (2005) · Zbl 1088.11001 [26] DOI: 10.1007/3-540-45455-1_19 · doi:10.1007/3-540-45455-1_19 [27] DOI: 10.1007/BFb0099440 · doi:10.1007/BFb0099440 [28] Chao, Advances in cryptology–ASIACRYPT’98 pp 95– (1998) · doi:10.1007/3-540-49649-1_9 [29] Buchmann, Binary quadratic forms: an algorithmic approach (2007) · Zbl 1125.11028 · doi:10.1007/978-3-540-46368-9_2 [30] von zur Gathen, Modern computer algebra (2003) [31] DOI: 10.1090/S0025-5718-2011-02508-1 · Zbl 1267.11125 · doi:10.1090/S0025-5718-2011-02508-1 [32] Leendert, Algebra I (1991) [33] DOI: 10.1090/S0025-5718-08-02091-7 · Zbl 1223.11073 · doi:10.1090/S0025-5718-08-02091-7 [34] DOI: 10.1090/S0025-5718-10-02356-2 · Zbl 1225.11163 · doi:10.1090/S0025-5718-10-02356-2 [35] DOI: 10.1016/j.jnt.2009.11.003 · Zbl 1225.11085 · doi:10.1016/j.jnt.2009.11.003 [36] DOI: 10.1090/S0025-5718-2010-02373-7 · Zbl 1231.11144 · doi:10.1090/S0025-5718-2010-02373-7 [37] DOI: 10.1090/S0025-5718-06-01849-7 · Zbl 1183.11080 · doi:10.1090/S0025-5718-06-01849-7 [38] Serre, Algebraic number theory (1967) [39] Schönhage, International Symposium on Symbolic and Algebraic Computation–ISSAC’91 pp 128– (1991) This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.