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

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

2001-11-13

arxiv.org/abs/math/0111159v2

Mathematics

Number Theory

14 pages, complexity analysis redone, several sections rewritten

Scientific paper

Elliptic curves with a known number of points over a given prime field with n elements 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 H(X) for a fundamental discriminant D. The usual way is to compute H(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 H(X) modulo n directly from the knowledge of H(X) modulo enough small primes. Our complexity analysis suggests that asymptotically our algorithm is an improvement over previously known methods.

Affiliated with

Also associated with

No associations

Rating

Constructing elliptic curves with a known number of points over a prime field does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Constructing elliptic curves with a known number of points over a prime field, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Constructing elliptic curves with a known number of points over a prime field will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-355753