Welcome to the resource topic for 2001/096
Title:
Constructing elliptic curves with a given number of points over a finite field
Authors: Amod Agashe, Kristin Lauter, 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.
ePrint: https://eprint.iacr.org/2001/096
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .