International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Computing Hilbert Class Polynomials

Authors:
Juliana Belding
Reinier Broker
Andreas Enge
Kristin E. Lauter
Download:
URL: http://eprint.iacr.org/2008/062
Search ePrint
Search Google
Abstract: We present and analyze two algorithms for computing the Hilbert class polynomial H_D(X). The first is a p-adic lifting algorithm for inert primes p in the order of discriminant D < 0. The second is an improved Chinese remainder algorithm which uses the class group action on CM-curves over finite fields. Our run time analysis gives tighter bounds for the complexity of all known algorithms for computing H_D(X), and we show that all methods have comparable run times.
BibTeX
@misc{eprint-2008-17739,
  title={Computing Hilbert Class Polynomials},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / elliptic curve cryptography, complex multiplication},
  url={http://eprint.iacr.org/2008/062},
  note={ klauter@microsoft.com 13913 received 4 Feb 2008},
  author={Juliana Belding and Reinier Broker and Andreas Enge and Kristin E. Lauter},
  year=2008
}