Computing Hilbert Class Polynomials

Juliana Belding 1 Reinier Bröker 2 Andreas Enge 3 Kristin Lauter 2
3 TANC - Algorithmic number theory for cryptology
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France
Abstract : We present and analyze two algorithms for computing the Hilbert class polynomial $H_D$ . 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$ , and we show that all methods have comparable run times.
Document type :
Conference papers
Complete list of metadatas

Cited literature [21 references]  Display  Hide  Download

https://hal.inria.fr/inria-00246115
Contributor : Andreas Enge <>
Submitted on : Thursday, February 7, 2008 - 2:50:25 PM
Last modification on : Monday, May 20, 2019 - 2:30:25 PM
Long-term archiving on : Monday, May 10, 2010 - 12:44:38 PM

Files

ants8.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00246115, version 1
  • ARXIV : 0802.0979

Collections

Citation

Juliana Belding, Reinier Bröker, Andreas Enge, Kristin Lauter. Computing Hilbert Class Polynomials. ANTS-VIII - Eighth Algorithmic Number Theory Symposium, May 2008, Banff, Canada. pp.282-295. ⟨inria-00246115⟩

Share

Metrics

Record views

574

Files downloads

278