Re: Fwd: Polrootsmod query

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

On Sat, Mar 12, 2011 at 02:03:40PM +0000, James Wanless wrote:
> Just realized I (probably?) sent this to the wrong list - I'll try
> and get it right in future!
>
> >Why is PARI's implementation of polrootsmod so fast??? :)))
> >I've implemented my own version using GMP and Algorithm 1.6.1 of
> >Cohen ACCANT, but PARI's seems order(s) of magnitude faster.
> >What algorithm does polrootsmod use, pls? Maybe Cantor-Zassenhaus
> >split etc., ie Cohen Algorithms 3.4.x, using matrices?? I've
> >looked at PARI's code and haven't (yet?) understood it, despite
> >noticing a few references to 'Berlekamp'...

Hello James,

THe relevant C function is FpX_roots_i.
PARI use Cantor-Zassenhauss and follow essentially Algorithm 1.6.1.
Most of the time is spend in the computation of (X mod (p,P))^p 
(see remark (2) page 38). For that you need one of the algorithms
of section 1.2 (binary powering).
You also need to implement fast polynomial arithmetic over Fp[X].

Note that PARI 2.4.3 is faster than PARI 2.3.5.

Cheers,
Bill.