Computing Hilbert Class Polynomials - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2008

Computing Hilbert Class Polynomials

Juliana Belding
  • Fonction : Auteur
  • PersonId : 846666
Reinier Bröker
  • Fonction : Auteur
  • PersonId : 846667
Andreas Enge
Kristin Lauter
  • Fonction : Auteur
  • PersonId : 846668

Résumé

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.
Fichier principal
Vignette du fichier
ants8.pdf (228.32 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

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

Identifiants

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

Citer

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⟩
343 Consultations
830 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More