Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Efficient CM-constructions of elliptic curves over finite fields

Authors: Reinier Bröker and Peter Stevenhagen
Journal: Math. Comp. 76 (2007), 2161-2179
MSC (2000): Primary 14H52; Secondary 11G15
Published electronically: May 3, 2007
MathSciNet review: 2336289
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We present an algorithm that, on input of an integer $ N\ge 1$ together with its prime factorization, constructs a finite field $ \mathbf{F}$ and an elliptic curve $ E$ over $ \mathbf{F} $ for which $ E({\mathbf{F} })$ has order $ N$. Although it is unproved that this can be done for all $ N$, a heuristic analysis shows that the algorithm has an expected run time that is polynomial in $ 2^{\omega (N)}\log N$, where $ \omega (N)$ is the number of distinct 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. We illustrate the efficiency of the algorithm by constructing elliptic curves with point groups of order $ N=10^{2004}$ and $ N=$nextprime$ (10^{2004})=10^{2004}+4863$.

References [Enhancements On Off] (What's this?)

  • 1. M. Agrawal, N. Kayal, N. Saxena, Primes is in P, Annals of Mathematics 160 (2004), 781-793. MR 2123939 (2006a:11170)
  • 2. R. C. Baker, G. Harman, J. Pintz, The difference between consecutive primes II, Proc. London Math. Soc. (3) 83 (2001), 532-562. MR 1851081 (2002f:11125)
  • 3. D. Bernstein, Proving primality in essentially quartic random time, Math. Comp., to appear.
  • 4. R. Bröker, Constructing elliptic curves of prescribed order, Ph.D. Thesis, Universiteit Leiden, 2006. See
  • 5. R. Bröker, P. Stevenhagen, Elliptic curves with a given number of points, Algorithmic Number Theory Symposium VI, Springer Lecture Notes in Computer Science, vol. 3076, 2004, pp. 117-131. MR 2137348 (2005m:11113)
  • 6. J. Buhler, S. Wagon, Basic algorithms in number theory, Surveys in Algorithmic Number Theory, Cambridge University Press, 2006.
  • 7. H. Cohen, A course in computational algebraic number theory, Springer Graduate Texts in Mathematics, vol. 138, 1996. MR 1228206 (94i:11105)
  • 8. J.-M. Couveignes, T. Henocq, Action of modular correspondences around CM points, Algorithmic Number Theory Symposium V, Springer Lecture Notes in Computer Science, vol. 2369, 2002, pp. 234-243. MR 2041087 (2005b:11077)
  • 9. A. Enge, The complexity of class polynomial computations via floating point approximations, preprint, January 2006.
  • 10. J. von zur Gathen, J. Gerhard, Modern computer algebra, Cambridge University Press, 1999. MR 1689167 (2000j:68205)
  • 11. P. Gaudry, A comparison and a combination of SST and AGM algorithms for counting points of elliptic curves in characteristic 2, ASIACRYPT 2002, Springer Lecture Notes in Computer Science, vol. 2501, 2002, pp. 311-327. MR 2087393 (2005h:11124)
  • 12. A. C. P. Gee, P. Stevenhagen, Generating class fields using Shimura reciprocity, Algorithmic Number Theory Symposium III, Springer Lecture Notes in Computer Science, vol. 1423, 1998, pp. 441-453. MR 1726092 (2000m:11112)
  • 13. A. Ivic, The theory of the Riemann Zeta-Function with applications, Wiley, New York, 1985. MR 792089 (87d:11062)
  • 14. K. Kedlaya, Counting points on hyperelliptic curves using Monsky-Washnitzer cohomology, Journal Ramanujan Mathematical Society 16 (2002), 323-338. MR 1877805 (2002m:14019)
  • 15. E. Konstantinou, Y. C. Stamatiou, C. D. Zaroliagis, On the construction of prime order elliptic curves, Progress in cryptology--INDOCRYPT 2003, Springer Lecture Notes in Computer Science 2904, 2003, pp. 309-322. MR 2092390 (2005k:14052)
  • 16. G.-J. Lay, H. G. Zimmer, Constructing elliptic curves with given group order over large finite fields, Algorithmic Number Theory Symposium I, Springer Lecture Notes in Computer Science, 1994. MR 1322728 (96a:11054)
  • 17. H. W. Lenstra, C. Pomerance, A rigorous time bound for factoring integers, J. Amer. Math. Soc. 5 (1992), 483-516. MR 1137100 (92m:11145)
  • 18. H. W. Lenstra, C. Pomerance, Primality testing with Gaussian periods, To appear.
  • 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).
  • 21. T. Satoh, The canonical lift of an ordinary elliptic curve over a finite field and its point counting, Journal Ramanujan Mathematical Society 15 (2000), 247-270. MR 1801221 (2001j:11049)
  • 22. E. Savas, T. A. Schmidt, Ç. K. Koç, Generating elliptic curves of prime order, Cryptographic hardware and embedded systems--CHES 2001 (Paris), Springer Lecture Notes in Computer Science 2162, 2001, pp. 142-158. MR 1945401 (2003m:14037)
  • 23. R. Schertz, Weber's class invariants revisited, J. Théorie des Nombres de Bordeaux 14 (2002), 325-343. MR 1926005 (2003j:11139)
  • 24. R. Schoof, Elliptic Curves over Finite Fields and the Computation of Square Roots mod $ p$, Math. Comp. 44 (1985), 483-494. MR 777280 (86e:11122)
  • 25. R. Schoof, Counting points on elliptic curves over finite fields, J. Théorie des Nombres de Bordeaux 7 (1995), 219-254. MR 1413578 (97i:11070)
  • 26. J. H. Silverman, The arithmetic of elliptic curves, Springer Graduate Texts in Mathematics, vol. 106, 1986. MR 817210 (87g:11070)
  • 27. P. Stevenhagen, Hilbert's 12th problem, complex multiplication and Shimura reciprocity, Class field theory - its centenary and prospect, ed. K. Miyake, Adv. studies in pure math., vol. 30, 2001, pp. 161-176. MR 1846457 (2002i:11110)
  • 28. H. P. F. Swinnerton-Dyer, An application of computing to class field theory, Algebraic Number Theory, ed. J. W. S. Cassels & A. Fröhlich, Academic Press, 1967. MR 0219514 (36:2595)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 14H52, 11G15

Retrieve articles in all journals with MSC (2000): 14H52, 11G15

Additional Information

Reinier Bröker
Affiliation: Mathematisch Instituut, Universiteit Leiden, Postbus 9512, 2300 RA Leiden, The Netherlands.
Address at time of publication: Department of Mathematics and Statistics, University of Calgary, 2500 University Drive NW, Calgary, Alberta, Canada T2N 1N4

Peter Stevenhagen
Affiliation: Mathematisch Instituut, Universiteit Leiden, Postbus 9512, 2300 RA Leiden, The Netherlands.

Received by editor(s): November 11, 2005
Received by editor(s) in revised form: June 9, 2006
Published electronically: May 3, 2007
Article copyright: © Copyright 2007 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society