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, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR7161
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.
Type de document :
Communication dans un congrès
Alfred J. van der Poorten, Andreas Stein. ANTS-VIII - Eighth Algorithmic Number Theory Symposium, May 2008, Banff, Canada. Springer-Verlag, 5011, pp.282-295, 2008, Lecture Notes in Computer Science
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00246115
Contributeur : Andreas Enge <>
Soumis le : jeudi 7 février 2008 - 14:50:25
Dernière modification le : jeudi 10 mai 2018 - 02:06:31
Document(s) archivé(s) le : lundi 10 mai 2010 - 12:44:38

Fichiers

ants8.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

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

Collections

Citation

Juliana Belding, Reinier Bröker, Andreas Enge, Kristin Lauter. Computing Hilbert Class Polynomials. Alfred J. van der Poorten, Andreas Stein. ANTS-VIII - Eighth Algorithmic Number Theory Symposium, May 2008, Banff, Canada. Springer-Verlag, 5011, pp.282-295, 2008, Lecture Notes in Computer Science. 〈inria-00246115〉

Partager

Métriques

Consultations de la notice

484

Téléchargements de fichiers

156