CryptoDB
Computing Hilbert Class Polynomials
Authors: | |
---|---|
Download: | |
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 }