Re: Hilbert class polynomial roots mod q

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

On Fri, Jul 08, 2022 at 11:36:51AM +0200, Karim Belabas wrote:
> * Karim Belabas [2022-07-08 11:26]:
> [...]
> > and in fact just computing x^p mod T is the bottleneck (deg T ~ 5, p ~ 2^32);
> [...]
> Just to be clear: the computation is x^p mod (T,p) and is done using a
> sliding window algorithm, naive polynomial arithmetic over F_p, and
> naive F_p arithmetic [ deg(T) is too small to make Barett reduction useful ]
> 
> It's the function Flxq_powu() in case anybody's interested.

Sutherland code hardcode the formulae for Flxq_mul for all polynomials of
degree < 100.

Cheers,
Bill.

PS: I have made a new branch bill-parpolclass