Re: How to calculate lower degree factors of elldivpol(e,100)

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

On Wed, Jun 12, 2013 at 05:52:07PM +0200, Karim Belabas wrote:
>     K.B.
> 
> P.S. Actually, your example exhibits a problem. When monitoring the progress of
> this particular computation, all 6 factors are found in 12 minutes on my
> laptop, and more than half of this time (7 minutes) is spent ... factoring f
> mod 31 using Berlekamp algorithm. This is rather silly since this is supposed
> to be the trivial part of the algorithm and factorcantor() can do the same in
> less than 10 seconds. That's because we quickly find lots of factors of small
> degree here, but even for an irreducible polynomial of degree 3600,
> factorcantor is still way faster than Berlekamp.

There seems to be a performance issue in factorcantor: the function
Flx_split() does not use a random polynomial w, whcih seems to slow things
down a lot. With this change

-    w = Flx_rem(stoFlx(m,p,v),*t, p);
+    w = Flx_rem(random_Flx(dv,v,p),*t, p);

factorcantor is about 4 time faster on this example.

Cheers,
Bill.