Re: Hilbert class polynomial roots mod q

[pari@jvdsn.com]

Hi Andreas,

As you probably know, the CM discriminant is linearly related to the 
target elliptic curve base ring modulus. Contemporaneous curves use 
256-bit+ fields, but I think that this discriminant size is far out of 
reach right now. Still, I'm interested in the most efficient 
implementations and having these easily available (e.g. in the PARI/GP 
interface).

Regarding the time complexity: I'm not very familiar with the 
theoretical details, but this does sound plausible to me. As you 
mentioned, larger coefficients require (as you mentioned) much more 
space, but mathematical operations also take longer on large 
arbitrary-precision integers. That's why I think there could also be 
significant time savings if the coefficients could be reduced mod q 
while the polynomial is being computed.

For example, using D = -4506399751 and q = 162230391061 (38-bit prime), 
I obtain the following results (with the Weber function invariant):

* 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. Perhaps another question is why the PARI/GP implementation is 
so inefficient compared to the original implementation it was adapted from.

Kind regards,
Joachim Vandersmissen

On 6/07/2022 10:26, Andreas Enge wrote:
> Hello,
>
> Am Tue, Jul 05, 2022 at 09:03:10PM +0200 schriebpari@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