Computing Hilbert Class Polynomials

Juliana Belding; Reinier Broker; Andreas Enge; Kristin Lauter

Paper 2008/062 Original: eprint.iacr.org/2008/062 ↗

Computing Hilbert Class Polynomials

Juliana Belding

Reinier Broker

Andreas Enge

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): PDF
Category: Public-key cryptography
Publication info: Preprint.
History: 2008-02-11: last updated; 2008-02-11: published
Short URL: https://ia.cr/2008/062
License: https://creativecommons.org/licenses/by/4.0/

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},
      url = {https://eprint.iacr.org/2008/062}
}