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

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

* Richard in Reading [2013-06-12 16:55]:
> I'm interested in the lower degree factors of various divison polynomials.
> I'm very impressed with PARI's ability to calculate with and then factorize a polynomials with large coefficients and degrees in the thousands. I have used the following:
> 
> e=ellinit("1584s1");
> f=elldivpol(e,100);
> fordiv(100,d,if(d!=100,f=f/gcd(f,elldivpol(e,d))));
> ff=factor(f);
> apply(poldegree,ff[,1]~)
> %1 = [100, 100, 200, 200, 1000, 2000]
> 
> But this is slow. Is there a more direct way to calculate the factors of degree 100 without getting the larger factors?

Not generically. Even for a well chose prime p, your f has *lots* of p-adic
factors (160), and we need to find minimal subsets whose product is rational.
At \g5, you see the following
    40 fact. of degree   5
    40 fact. of degree  10
    40 fact. of degree  25
    40 fact. of degree  50
...tried prime  31 (160 factors). Time = 1949

This is a hard combinatorial problem, which can nevertheless be solved in
polynomial time using variants of the LLL algorithms -- the particular
algorithm implemented in PARI is due to Mark van Hoeij and me.

In practice, as happens here, these algorithms find all factors simultaneously,
although one can (in principle) be lucky and find factors early on. So there's
no way to "target" low degree factors.

Cheers,

    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.

This is all the sillier when one considers that the above output
(40 fact. of degree 5, etc.) was obtained by running the first phase of
factorcantor() [ = distinct degree factorization ]. So we were in fact
almost done with the modular factorization at this point. I'll fix that.

--
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]
`