John Cremona on Thu, 13 Jun 2013 10:31:32 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: How to calculate lower degree factors of elldivpol(e,100) |
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] > ` >