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

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.