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

[John Cremona <john.cremona@gmail.com>]

A couple of comments:

1. Because of the nature of division polynomials, as soon as you have
one factor you can construct others from it:   the factor you have
will have as its roots the x(P) for some subset of the m-torsion
points (where you started with the m-division polynomial), and it is
not hard to create from that the factor whose roots are the x(2P) for
P in the same set.  In general this will be a different factor.

2. Possibly this is what Bill was meaning:   if m1 divides m2 then the
m1-div.pol. will divide the m2-div.pol.  You had the 100-div. pol.
and I would not ask to factor that directly, but would divide it by
the m-div.pol. for m=2,4,5,10,20,25,50 first (not literally of course,
I mean to use Mobius inversion).  If you want to do this a lot it
would be worth writing a separate function to return the poly whose
roots are x-coordinates of the points of exact order m.  I don't think
that has a name but it's the analogue of the cyclotomic polynomial
Phi(m) in relation to X^m-1.

3. You asked about evaluating the factors of the polynomials directly.
 Something which Another Package allows, which I have often found
useful, is that to give the (recursive) elldivpol function as its 3rd
parameter not a variable but essentially anything, including a number.
 So instead of

(09:29) gp > E = ellinit("11a1");
(09:29) gp > f=elldivpol(E,5);
(09:29) gp > subst(f,x,17)
%9 = 325329544366332

you could replace the last two lines with elldivpol(E,5,17).

Of course this might not give you what you want.

John

On 12 June 2013 16:52, Karim Belabas <Karim.Belabas@math.u-bordeaux1.fr> wrote:
> * 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]
> `
>