×

zbMATH — the first resource for mathematics

Efficient CM-constructions of elliptic curves over finite fields. (English) Zbl 1127.14022
The authors present an algorithm that, on input an integer \(N\geq 1\) together with its prime factorization, constructs a prime field \(\mathbb{F}_p\) and an elliptic curve \(E\) over \(\mathbb{F}_p\) for which \(E(\mathbb{F}_p)\) has order \(N\). The algorithm uses the typical CM method, but chooses a prime \(p\) leading to a relatively small class polynomial. The key idea is to find a small square-free integer \(d\geq1\) together with an algebraic integer \(\alpha\in K=\mathbb{Q}(\sqrt{-d})\) such that \(\text{N}_{K/\mathbb{Q}}(\alpha)=N\) and \(\text{N}_{K/\mathbb{Q}}(1-\alpha)=p\) is a prime.
There is no proof that such a pair \((d,\alpha)\) always exists, but under reasonable heuristic assumptions the run time is polynomial in \(2^{\omega(N)}\log N\), where \(\omega(N)\) is the number of prime factors of \(N\). In the cryptographically relevant case where \(N\) is prime an expected run time \(O((\log N)^{4+\varepsilon})\) can be achieved.

MSC:
14G15 Finite ground fields in algebraic geometry
11G15 Complex multiplication and moduli of abelian varieties
11G20 Curves over finite and local fields
94A60 Cryptography
14H52 Elliptic curves
Software:
ECPP
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, PRIMES is in P, Ann. of Math. (2) 160 (2004), no. 2, 781 – 793. · Zbl 1071.11070 · doi:10.4007/annals.2004.160.781 · doi.org
[2] R. C. Baker, G. Harman, and J. Pintz, The difference between consecutive primes. II, Proc. London Math. Soc. (3) 83 (2001), no. 3, 532 – 562. · Zbl 1016.11037 · doi:10.1112/plms/83.3.532 · doi.org
[3] D. Bernstein, Proving primality in essentially quartic random time, Math. Comp., to appear. · Zbl 1144.11085
[4] R. Bröker, Constructing elliptic curves of prescribed order, Ph.D. Thesis, Universiteit Leiden, 2006. See www.math.leidenuniv.nl/scripties/Broker.pdf.
[5] Reinier Bröker and Peter Stevenhagen, Elliptic curves with a given number of points, Algorithmic number theory, Lecture Notes in Comput. Sci., vol. 3076, Springer, Berlin, 2004, pp. 117 – 131. · Zbl 1207.11065 · doi:10.1007/978-3-540-24847-7_8 · doi.org
[6] J. Buhler, S. Wagon, Basic algorithms in number theory, Surveys in Algorithmic Number Theory, Cambridge University Press, 2006. · Zbl 1196.11170
[7] Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. · Zbl 0786.11071
[8] Jean-Marc Couveignes and Thierry Henocq, Action of modular correspondences around CM points, Algorithmic number theory (Sydney, 2002) Lecture Notes in Comput. Sci., vol. 2369, Springer, Berlin, 2002, pp. 234 – 243. · Zbl 1057.11026 · doi:10.1007/3-540-45455-1_19 · doi.org
[9] A. Enge, The complexity of class polynomial computations via floating point approximations, preprint, January 2006.
[10] Joachim von zur Gathen and Jürgen Gerhard, Modern computer algebra, Cambridge University Press, New York, 1999. · Zbl 0936.11069
[11] Pierrick Gaudry, A comparison and a combination of SST and AGM algorithms for counting points of elliptic curves in characteristic 2, Advances in cryptology — ASIACRYPT 2002, Lecture Notes in Comput. Sci., vol. 2501, Springer, Berlin, 2002, pp. 311 – 327. · Zbl 1065.11098 · doi:10.1007/3-540-36178-2_20 · doi.org
[12] Alice Gee and Peter Stevenhagen, Generating class fields using Shimura reciprocity, Algorithmic number theory (Portland, OR, 1998) Lecture Notes in Comput. Sci., vol. 1423, Springer, Berlin, 1998, pp. 441 – 453. · Zbl 0912.11045 · doi:10.1007/BFb0054883 · doi.org
[13] Aleksandar Ivić, The Riemann zeta-function, A Wiley-Interscience Publication, John Wiley & Sons, Inc., New York, 1985. The theory of the Riemann zeta-function with applications. · Zbl 0556.10026
[14] Kiran S. Kedlaya, Counting points on hyperelliptic curves using Monsky-Washnitzer cohomology, J. Ramanujan Math. Soc. 16 (2001), no. 4, 323 – 338. · Zbl 1066.14024
[15] Elisavet Konstantinou, Yannis C. Stamatiou, and Christos Zaroliagis, On the construction of prime order elliptic curves, Progress in cryptology — INDOCRYPT 2003, Lecture Notes in Comput. Sci., vol. 2904, Springer, Berlin, 2003, pp. 309 – 322. · Zbl 1123.14300 · doi:10.1007/978-3-540-24582-7_23 · doi.org
[16] Georg-Johann Lay and Horst G. Zimmer, Constructing elliptic curves with given group order over large finite fields, Algorithmic number theory (Ithaca, NY, 1994) Lecture Notes in Comput. Sci., vol. 877, Springer, Berlin, 1994, pp. 250 – 263. · Zbl 0833.11024 · doi:10.1007/3-540-58691-1_64 · doi.org
[17] H. W. Lenstra Jr. and Carl Pomerance, A rigorous time bound for factoring integers, J. Amer. Math. Soc. 5 (1992), no. 3, 483 – 516. · Zbl 0770.11057
[18] H. W. Lenstra, C. Pomerance, Primality testing with Gaussian periods, To appear. · Zbl 1027.68984
[19] P. Mihailescu, R. M. Avanzi, Efficient ‘quasi’-deterministic primalisty test improving AKS, preprint (2003).
[20] F. Morain, Implementing the asymptotically fast version of the elliptic curve primality proving algorithm, preprint, arXiv:math.NT/0502097 (2005). · Zbl 1127.11084
[21] Takakazu Satoh, The canonical lift of an ordinary elliptic curve over a finite field and its point counting, J. Ramanujan Math. Soc. 15 (2000), no. 4, 247 – 270. · Zbl 1009.11051
[22] Erkay Savaş, Thomas A. Schmidt, and Çetin K. Koç, Generating elliptic curves of prime order, Cryptographic hardware and embedded systems — CHES 2001 (Paris), Lecture Notes in Comput. Sci., vol. 2162, Springer, Berlin, 2001, pp. 142 – 158. · Zbl 1012.94546 · doi:10.1007/3-540-44709-1_13 · doi.org
[23] Reinhard Schertz, Weber’s class invariants revisited, J. Théor. Nombres Bordeaux 14 (2002), no. 1, 325 – 343 (English, with English and French summaries). · Zbl 1022.11056
[24] René Schoof, Elliptic curves over finite fields and the computation of square roots mod \?, Math. Comp. 44 (1985), no. 170, 483 – 494. · Zbl 0579.14025
[25] René Schoof, Counting points on elliptic curves over finite fields, J. Théor. Nombres Bordeaux 7 (1995), no. 1, 219 – 254. Les Dix-huitièmes Journées Arithmétiques (Bordeaux, 1993). · Zbl 0852.11073
[26] Joseph H. Silverman, The arithmetic of elliptic curves, Graduate Texts in Mathematics, vol. 106, Springer-Verlag, New York, 1986. · Zbl 0585.14026
[27] Peter Stevenhagen, Hilbert’s 12th problem, complex multiplication and Shimura reciprocity, Class field theory — its centenary and prospect (Tokyo, 1998) Adv. Stud. Pure Math., vol. 30, Math. Soc. Japan, Tokyo, 2001, pp. 161 – 176. · Zbl 1097.11535
[28] H. P. F. Swinnerton-Dyer, An application of computing to class field theory, Algebraic Number Theory (Proc. Instructional Conf., Brighton, 1965), Thompson, Washington, D.C., 1967, pp. 280 – 291.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.