Re: Work on polrootsff/factorff

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

On Sat, Dec 01, 2012 at 09:52:39PM +0100, Bill Allombert wrote:
> Dear PARI developers,
> 
> I am working on improving factorff and polrootsff which have historically
> been quite slow in PARI.
> 
> I join two benchmarks. The first file is for Trager algorithm (default) and the
> second for Berlekamp algorithm.  The third column is polrootsff timings and the
> fourth is factorff timings.
> 
> We see that Berlekamp is consistently much faster than Trager for large degree.
> 
> There is three oddities:
> 1) We did not implement Berlekamp over F_2^n yet, so we are still using Trager
> for that case in the second file, so we get indentical results.
> 
> 2) We have dedicated code for Trager over F_2^n but not for polrootsff yet, so
> factorff is much faster.

Unfortunately implementing Berlekamp over F_2^n is quite a bit of work.
(We do not have yet implemented the class F2xqX_*)

> 3) For degree 2 polynomials, polrootsff is much slower than factorff, because
> the square root function over Fq is slow for large degree.

I found a reference for the algorithm:
<http://www.ma.utexas.edu/users/voloch/Preprints/roots.pdf>

Cheers,
Bill.