Constructing elliptic curves with a known number of points over a prime field

Abstract

Abstract. Elliptic curves with a known number of points over a given prime field Fn are often needed for use in cryptography. 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 a root modulo n of the Hilbert class polynomial HD(X) for a fundamental discriminant D. The usual way is to compute HD(X) over the integers and then to find the root modulo n. We present a modified version of the Chinese remainder theorem (CRT) to compute HD(X) modulo n directly from the knowledge of HD(X) modulo enough small primes. Our complexity analysis suggests that asymptotically our algorithm is an improvement over previously known methods. 1.