### Computing Hilbert Class Polynomials

Juliana Belding, Reinier Broker, 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.

##### Metadata
Available format(s)
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
elliptic curve cryptographycomplex multiplication
Contact author(s)
klauter @ microsoft com
History
2008-02-11: received
Short URL
https://ia.cr/2008/062
License

CC BY

BibTeX

@misc{cryptoeprint:2008/062,
author = {Juliana Belding and Reinier Broker and Andreas Enge and Kristin Lauter},
title = {Computing Hilbert Class Polynomials},
howpublished = {Cryptology ePrint Archive, Paper 2008/062},
year = {2008},
note = {\url{https://eprint.iacr.org/2008/062}},
url = {https://eprint.iacr.org/2008/062}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.