×

Accelerating the CM method. (English) Zbl 1343.11098

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.

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
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.