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

[Bill Allombert <Bill.Allombert@math.u-bordeaux1.fr>]

On Wed, Jun 12, 2013 at 03:55:01PM +0100, Richard in Reading wrote:
> 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?

First you should use Moebius inversion formula, 
my(p=1);fordiv(100,d,my(m=moebius(d));if(!m,next);my(P=elldivpol(e,100/d));if(m>0,p*=P,p/=P));p

Second, why do you expect the polynomial to have small degree factors ?
This is the key to find them more quickly.

Cheers,
Bill.