IACR paper details
Title  Constructing elliptic curves with a given number of points over a finite field 

Booktitle  IACR Eprint archive 

Pages  

Year  2001 

URL  http://eprint.iacr.org/2001/096 

Author  Amod Agashe 

Author  Kristin Lauter 

Author  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.


Search for the paper
@misc{eprint200111508,
title={Constructing elliptic curves with a given number of points over a finite field},
booktitle={IACR Eprint archive},
keywords={publickey cryptography / elliptic curve cryptosystem},
url={http://eprint.iacr.org/2001/096},
note={submitted for publication klauter@microsoft.com 11639 received 13 Nov 2001},
author={Amod Agashe and Kristin Lauter and Ramarathnam Venkatesan},
year=2001
}
Download a complete BibTeX file.