Re: Hilbert class polynomial roots mod q

[Karim Belabas <Karim.Belabas@math.u-bordeaux.fr>]

* 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.

Maybe hardcoding (and optimizing) multiplication of small degree
polynomials and Euclidean division would be enough to bridge the
performance gap.

Cheers,

    K.B.
--
Karim Belabas, IMB (UMR 5251), Université de Bordeaux
Vice-président en charge du Numérique
T: (+33) 05 40 00 29 77; http://www.math.u-bordeaux.fr/~kbelabas/
`