Re: Hilbert class polynomial roots mod q

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Mon, Jul 04, 2022 at 12:28:35AM +0200, pari@jvdsn.com wrote:
> 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.

This is only implemented for modular polynomials (polmodular).
We did not find the size of class polynomials to be a limitation for
our applications.

> 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.

Indeed it is not implemented. Does Sutherland published an
implementation ? Then we could adpat his code, as we did for polclass.

> 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). 

The function only works for small p satisfying some technical
conditions.

> 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?

The opposite happens: polclass uses the function polclass_roots_modp for
various small p and uses the CRT to recover the class polynomial.

Cheers,
Bill