Re: Hilbert class polynomial roots mod q

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

On Wed, Jul 06, 2022 at 10:26:56AM +0200, Andreas Enge wrote:
> Hello,
> 
> Am Tue, Jul 05, 2022 at 09:03:10PM +0200 schrieb pari@jvdsn.com:
> > For Complex Multiplication, the discriminants can
> > become very large, so this would be a big performance improvement.
> 
> I am a bit surprised that you encounter a performance limitation. What
> exactly is the size of discriminants you are interested in?
> 
> The time complexity for the mod P class polynomial is the same, it is
> just the memory requirement that decreases. However, about ten years ago
>    https://hal.inria.fr/inria-00001040/
> I have computed a class polynomial of degree 100000 for a discriminant of
> about -2*10^9; the paper states that it "uses over 5 GB as an uncompressed
> text file and is computed in about 3 days", for a serial computation on
> one core. Do you want to go much beyond this?
> 
> You may want to try my software CM:
>    https://www.multiprecision.org/cm/
> I just checked with one of my favourite discriminants,
> -23512271 or 4 times this, both with a class number of 10000,
> with a Weber invariant. CM is a little bit faster on my laptop than GP:
> 
> ? f=polclass (-6961631, 1);
> cpu time = 1min, 16,564 ms, real time = 1min, 16,620 ms.

For the record: this is not the case, the time on my laptop is
  cpu time 3,665 ms, real time 3,736 ms.

which is still much slower than Sutherland code, but at least not
completly ridiculous.

Indepently, in commit 15c47e34a2e1a1865d0 I have changed polclass to be parallel.

So for example, on a 20 cores system:

? polclass (-23512271, 1)
  cpu time 1min, 55,255 ms, real time 8,886 ms.

Cheers,
Bill