Re: Hilbert class polynomial roots mod q

[Andreas Enge <andreas.enge@inria.fr>]

Hello Joachim,

Am Thu, Jul 07, 2022 at 08:16:44PM +0200 schrieb pari@jvdsn.com:
> * PARI/GP polclass: out of memory after about 20 minutes (PARI stack size
> set to 9100001280 (8678.438 Mbytes))
> * Sutherland's classpoly without providing q: 149.9s
> * Sutherland's classpoly with providing q: 129.2s
> 
> As you can see, Sutherland's implementation is somewhat faster if q is
> provided.

indeed, somewhat faster, but not radically so. In any case, Sutherland's
implementation is really fast, with or without q. And if I am not mistaken,
it is not even parallelised.

My CM software needs 2700s (on one core of my laptop) for this polynomial
of degree 38022 and with a precision of 57641 bits (which tends to be very
close to the size of the largest coefficient, which has 52360 bits here). 
The text file storing the polynomial in GP format takes about 500MB.

> Perhaps another question is why the PARI/GP implementation is so
> inefficient compared to the original implementation it was adapted from.

It should definitely not run out of memory on this size of polynomial.
I would call this a bug. Or at least an opportunity for improvement!

Andreas