Re: Hilbert class polynomial roots mod q

[pari@jvdsn.com]

Hi Bill,

Thanks for your response.

I contacted Andrew Sutherland about the implementation for the second 
paper. He told me it's currently not publicly available. However, your 
comment did point me to his implementation of the first paper (which I 
was unaware of, thanks!). I will have a close look at his implementation 
and the PARI/GP implementation, to see if there's a straightforward way 
to add a mod P functionality to PARI/GP. For Complex Multiplication, the 
discriminants can become very large, so this would be a big performance 
improvement.

Do you perhaps know why the full algorithm (i.e. with the mod P 
functionality) was not implemented in PARI/GP? In fact, I would think 
it's easier to adapt the full algorithm rather than extracting some 
partial implementation from Sutherland's code. I'm trying to understand 
if there's any major obstacles here.

Kind regards,
Joachim

On 4/07/2022 22:15, Bill Allombert wrote:
> 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