Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



A $ p$-adic algorithm to compute the Hilbert class polynomial

Author: Reinier Bröker
Journal: Math. Comp. 77 (2008), 2417-2435
MSC (2000): Primary 11G15
Published electronically: April 23, 2008
MathSciNet review: 2429891
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Classically, the Hilbert class polynomial $ P_{\Delta }\in \mathbf{Z} [X]$ of an imaginary quadratic discriminant $ \Delta $ is computed using complex analytic techniques. In 2002, Couveignes and Henocq suggested a $ p$-adic algorithm to compute $ P_{\Delta }$. Unlike the complex analytic method, it does not suffer from problems caused by rounding errors. In this paper we give a detailed description of the algorithm in the paper by Couveignes and Henocq, and our careful study of the complexity shows that, if the Generalized Riemann Hypothesis holds true, the expected runtime of the $ p$-adic algorithm is $ O(\vert\Delta \vert(\log \vert\Delta \vert)^{8+\varepsilon })$ instead of $ O(\vert\Delta \vert^{1+\varepsilon })$. We illustrate the algorithm by computing the polynomial $ P_{-639}$ using a $ 643$-adic algorithm.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11G15

Retrieve articles in all journals with MSC (2000): 11G15

Additional Information

Reinier Bröker
Affiliation: Department of Mathematics and Statistics, University of Calgary, 2500 University Drive NW, Calgary, AB T2N 1N4, Canada
Address at time of publication: Microsoft Research, One Microsoft Way, Redmond, Washington 98052

Received by editor(s): November 10, 2006
Received by editor(s) in revised form: June 27, 2007
Published electronically: April 23, 2008
Article copyright: © Copyright 2008 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society