|Bill Allombert on Sat, 12 Mar 2011 16:12:57 +0100|
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
|Re: Fwd: Polrootsmod query|
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.