Computing Hilbert Class Polynomials
| hal.structure.identifier | Department of Mathematics [College Park] | |
| dc.contributor.author | BELDING, Juliana | |
| hal.structure.identifier | Microsoft Research [Redmond] | |
| dc.contributor.author | BRÖKER, Reinier | |
| hal.structure.identifier | Algorithmic number theory for cryptology [TANC] | |
| dc.contributor.author | ENGE, Andreas | |
| hal.structure.identifier | Microsoft Research [Redmond] | |
| dc.contributor.author | LAUTER, Kristin | |
| dc.contributor.editor | Alfred J. van der Poorten, Andreas Stein | |
| dc.date.issued | 2008 | |
| dc.date.conference | 2008-05-17 | |
| dc.description.abstractEn | 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. | |
| dc.language.iso | en | |
| dc.publisher | Springer-Verlag | |
| dc.subject.en | class polynomial | |
| dc.subject.en | p-adic lifting | |
| dc.subject.en | algorithm | |
| dc.subject.en | complexity | |
| dc.title.en | Computing Hilbert Class Polynomials | |
| dc.type | Communication dans un congrès avec actes | |
| dc.subject.hal | Mathématiques [math]/Théorie des nombres [math.NT] | |
| dc.identifier.arxiv | 0802.0979 | |
| bordeaux.page | 282-295 | |
| bordeaux.volume | 5011 | |
| bordeaux.country | CA | |
| bordeaux.title.proceeding | ANTS-VIII - Eighth Algorithmic Number Theory Symposium | |
| bordeaux.conference.city | Banff | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | inria-00246115 | |
| hal.version | 1 | |
| hal.origin.link | https://hal.archives-ouvertes.fr//inria-00246115v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.date=2008&rft.volume=5011&rft.spage=282-295&rft.epage=282-295&rft.au=BELDING,%20Juliana&BR%C3%96KER,%20Reinier&ENGE,%20Andreas&LAUTER,%20Kristin&rft.genre=proceeding |
Fichier(s) constituant ce document
| Fichiers | Taille | Format | Vue |
|---|---|---|---|
|
Il n'y a pas de fichiers associés à ce document. |
|||