Re: Hilbert class polynomial roots mod q

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

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.

$ classpol -i weber -d 94049084 -v
--- Elapsed time: 33.6

Andreas