Cryptology ePrint Archive: Report 2008/062

Computing Hilbert Class Polynomials

Juliana Belding and Reinier Broker and Andreas Enge and Kristin Lauter

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.

Category / Keywords: public-key cryptography / elliptic curve cryptography, complex multiplication

Date: received 4 Feb 2008

Contact author: klauter at microsoft com

Available format(s): PDF | BibTeX Citation

Version: 20080211:105828 (All versions of this report)

Short URL: ia.cr/2008/062

Discussion forum: Show discussion | Start new discussion