|Bill Allombert on Sat, 15 Jun 2013 15:02:04 +0200|
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
|Re: How to calculate lower degree factors of elldivpol(e,100)|
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.