Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
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?)


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
Email: reinier@math.ucalgary.ca

Peter Stevenhagen
Affiliation: Mathematisch Instituut, Universiteit Leiden, Postbus 9512, 2300 RA Leiden, The Netherlands.
Email: psh@math.leidenuniv.nl

DOI: http://dx.doi.org/10.1090/S0025-5718-07-01980-1
PII: S 0025-5718(07)01980-1
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.