Re: Hilbert class polynomial roots mod q

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

On Fri, Jul 08, 2022 at 11:25:57AM +0200, Karim Belabas wrote:
> is still slow (23 minutes on my laptop) but requires less than 2GB,
> in fact a little more than 1GB. The output size (internal binary format, not
> text) is 231MB, so this is OK.
> 
> As far as speed is concerned, I see where the bottleneck is but am not
> familiar with the code either. We're computing modulo 1681 (32-bit)
> primes, which is enough to recognize 53792 bit coefficients, even closer
> to the optimal 52360 compared to 'cm'.
> 
> The computation modulo each such prime p is "too slow", which in turn
> boils down to computing roots mod p of small degree polynomials (say T)
> and in fact just computing x^p mod T is the bottleneck (deg T ~ 5, p ~ 2^32);
> not sure why we lose a factor 10 or so there, compared to Sutherland's code.

This is the bottleneck for us, but I doubt this explain the slowdown.
What we can try is to change T so that trace(Mod(x,T)) == 0
Also see commit ef7b2b9b091bbbbf27fd232727ce598de0b5be4d

Cheers,
Bill.