Paper 2001/096
Constructing elliptic curves with a given number of points over a finite field
Amod Agashe, Kristin Lauter, and Ramarathnam Venkatesan
Abstract
In using elliptic curves for cryptography, one often needs to construct elliptic curves with a given or known number of points over a given finite field. In the context of primality proving, Atkin and Morain suggested the use of the theory of complex multiplication to construct such curves. One of the steps in this method is the calculation of the Hilbert class polynomial $H_D(X)$ modulo some integer $p$ for a certain fundamental discriminant $D$. The usual way of doing this is to compute $H_D(X)$ over the integers and then reduce modulo $p$. But this involves computing the roots with very high accuracy and subsequent rounding of the coefficients to the closest integer. (Such accuracy issues also arise for higher genus cases.) We present a modified version of the Chinese remainder theorem (CRT) to compute $H_D(X)$ modulo $p$ directly from the knowledge of $H_D(X)$ modulo enough small primes. Our algorithm is inspired by Couveigne's method for computing square roots in the number field sieve, which is useful in other scenarios as well. It runs in heuristic expected time less than the CRT method in [CNST]. Moreover, our method requires very few digits of precision to succeed, and avoids calculating the exponentially large coefficients of the Hilbert class polynomial over the integers.
Metadata
 Available format(s)
 PS
 Category
 Publickey cryptography
 Publication info
 Published elsewhere. submitted for publication
 Keywords
 elliptic curve cryptosystem
 Contact author(s)
 klauter @ microsoft com
 History
 20011113: received
 Short URL
 https://ia.cr/2001/096
 License

CC BY
BibTeX
@misc{cryptoeprint:2001/096, author = {Amod Agashe and Kristin Lauter and Ramarathnam Venkatesan}, title = {Constructing elliptic curves with a given number of points over a finite field}, howpublished = {Cryptology ePrint Archive, Paper 2001/096}, year = {2001}, note = {\url{https://eprint.iacr.org/2001/096}}, url = {https://eprint.iacr.org/2001/096} }