inria-00246115, version 1
Computing Hilbert Class Polynomials
Juliana Belding
1Reinier Bröker 2Andreas Enge 3Kristin Lauter 2
ANTS-VIII - Eighth Algorithmic Number Theory Symposium 5011 (2008) 282-295
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.
- 1 : Department of Mathematics, University of Maryland
- University of Maryland
- 2 : Microsoft Research
- Microsoft
- 3 : TANC (INRIA Saclay - Ile de France)
- INRIA – Polytechnique - X – CNRS : UMR7161
- Domaine : Mathématiques/Théorie des nombres
- Mots-clés : class polynomial – p-adic lifting – algorithm – complexity
- inria-00246115, version 1
- http://hal.inria.fr/inria-00246115
- oai:hal.inria.fr:inria-00246115
- Contributeur : Andreas Enge
- Soumis le : Jeudi 7 Février 2008, 14:50:25
- Dernière modification le : Mercredi 13 Août 2008, 15:10:55
Documents associés
Exporter