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

[Karim Belabas <Karim.Belabas@math.u-bordeaux1.fr>]

* Bill Allombert [2013-06-15 15:02]:
> 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.

Agreed, same with itoFpX -> random_FpX in the same file. Old Pari code
sometimes limit arbitrarily our sampling spaces in probabilistic algorithms
(apparently in order to limit the object "sizes"), which is usually
detrimental to their efficiency.

Good catch !

    K.B.

P.S. This will not improve much on the original poster's problem though.
Switching from Berlekamp to (even an inefficient) Cantor-Zassenhaus will
already exhibit most of the achievable improvement.

--
Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite Bordeaux 1          Fax: (+33) (0)5 40 00 69 50
351, cours de la Liberation    http://www.math.u-bordeaux1.fr/~kbelabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux1.fr/  [PARI/GP]
`