[flint-devel] Z/pZ[x] factoring

[Bill H. <goo...@go...>]

I have been producing some timings for factoring polynomials over
Z/pZ[x] against a recent version of Magma.

Here is the graph:

http://sage.math.washington.edu/home/wbhart/zpfactor.png

It appears that Magma is thrashing us, even with all the recent
improvements to zmod_poly.

I don't know if Magma has been sped up or if we just mistimed in the
past, but towards the left of that diagram we are 2-5 times slower
than Magma, and on the right hand side it's more like 12 times slower.

The Berlekamp algorithm we use is a polynomial one, with a
Gauss-Jordan elimination somewhere along the way. But I think there is
a version of the algorithm which computes much more using matrix
algebra.

As FLINT is a long way away from having fast matrices over Z/pZ I
think it will be some time before we can beat Magma (again) on this
benchmark. This is a little disappointing, but I'm sure it can be
fixed in time.

Bill.