**Constructing elliptic curves with a given number of points over a finite field **

*Amod Agashe and 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.

**Category / Keywords: **public-key cryptography / elliptic curve cryptosystem

**Publication Info: **submitted for publication

**Date: **received 13 Nov 2001

**Contact author: **klauter at microsoft com

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation

**Version: **20011113:185947 (All versions of this report)

**Short URL: **ia.cr/2001/096

[ Cryptology ePrint archive ]