Hilbert class polynomial roots mod q

[pari@jvdsn.com]

Hi all,

In elliptic curve cryptography, the Complex Multiplication method is 
used to generate elliptic curves with some predefined properties. A key 
step in this process is computing the roots of a Hilbert class 
polynomial with discriminant D modulo q (where q is a prime, or perhaps 
even a prime power). I would like to use PARI/GP for this purpose.

PARI currently offers a function polclass, which computes the Hilbert 
class polynomial for a given discriminant D (H_D(X)). Looking at the 
implementation, this code seems to be based off Andrew Sutherland's 
"Computing Hilbert class polynomials with the Chinese Remainder Theorem" 
[0]. That paper presents an algorithm to compute H_D(X) module some 
integer P (= q). However, the polclass does not provide a parameter for 
the modulus. Therefore, the current approach would be:

1. Compute H_D(X) using polclass
2. Reduce H_D(X) mod q
3. Find the roots of H_D(X) mod q

The issue arises in step 1, which computes H_D(X) over the integers. For 
large Ds, this polynomial will be too big and take too long to generate. 
This is why computing H_D(X) mod P directly would be a big performance 
improvement. I'm wondering if it would be technically feasible to add 
the parameter P to this method? I'm not very familiar with the PARI 
internals, so right now the code is quite hard to read for me.

Actually, it would be even better if the roots of H_D(X) could be 
computed modulo P without even constructing (the coefficients of) the 
polynomial itself. Andrew Sutherland has a follow-up paper, 
"Accelerating the CM method" [1], which deals with this issue. I don't 
think this paper is currently implemented in PARI, but feel free to 
correct me if I'm wrong. Still, when I looked at the polclass code, I 
found a function called polclass_roots_modp. This function sounds very 
promising, but I don't know if it fully solves the problem (e.g. it has 
a lot more arguments than I would expect). So, my second question is: 
would it be technically feasible to make this function externally 
accessible, with a much simplified API that simply accepts the 
parameters D and P to directly compute the roots of H_D(X) mod P?

I would be open to making these changes myself, but as mentioned 
previously I have no experience with PARI code/internals. Perhaps 
someone else is more familiar with the polclass code and actually knows 
what is implemented where. Thanks in advance for any help.

Kind regards,
Joachim Vandersmissen

[0]: https://doi.org/10.48550/arXiv.0903.2785
[1]: https://doi.org/10.1112/S1461157012001015