pari on Tue, 05 Jul 2022 21:03:14 +0200


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: Hilbert class polynomial roots mod q


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