Karim Belabas on Wed, 12 Jun 2013 17:52:22 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: How to calculate lower degree factors of elldivpol(e,100) |
* 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] `