Richard in Reading on Fri, 14 Jun 2013 13:46:09 +0200


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Targeting low degree factors of division polynomials


In a previous email Karim mentions that in principle it's possible for the polynomial factorization process to find low degree factors at an earlier stage but in practice they'll find all the factors simultaneously.
Looking at the log for the following commands using \g5

e=ellinit("784h1");f=factor(elldivpol(e,128)/elldivpol(e,64));

the two factors of degree 64 are found under the line
"### K = 1, 96 combinations"
and the factor of degree 128 is found under the line
"### K = 2, 4371 combinations"
the remaining factors of degree 256,512,1024,2048 and 2048 are found at the end after the LLL step.

So this is an example of low-degree factors being found more easily.
Without me having to trawl through the source code to work out how the factoring works, could someone please infer from the log file what must be happening to drop these small factors out early so I can attempt to exploit this when factoring much larger degree division polynomials? 

Similar behaviour exists for factor(elldivpol(ee,125)/elldivpol(ee,25)) but I have lost the relevant curve. I take this to mean that this behaviour is unlikely to be purely coincidental.

Thanks!

Richard Heylen