Computing Hilbert Class Polynomials - Archive ouverte HAL Access content directly
Conference Papers Year : 2008

## Computing Hilbert Class Polynomials

(1) , (2) , (3) , (2)
1
2
3
Juliana Belding
• Function : Author
• PersonId : 846666
Reinier Bröker
• Function : Author
• PersonId : 846667
Andreas Enge
Kristin Lauter
• Function : Author
• PersonId : 846668

#### 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.

#### Domains

Mathematics [math] Number Theory [math.NT]

### Dates and versions

inria-00246115 , version 1 (07-02-2008)

### Identifiers

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

### Cite

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⟩

### Export

BibTeX TEI Dublin Core DC Terms EndNote Datacite

335 View