Re: Calculate lower degree factors of elldivpol(e,100)

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

Richard, I am cc-ing pari-users since this question originated there,
though my ideas here do not have anything to do with the
technicatilties of factorisation algorithms, or useful shortcuts such
as the one Karim posted.

Let's agree to call here the "degree" of a point the degree of the
extension obtained by adjoining its x-coordinate (though the actual
degree of definition of thepoint may be double that), and let's call
the exact-m-division polynomial of E the polynomial whose roots are
the points of exact order m (whereas the usual division poly has as
roots the c-coords of the points of order dividing m).

You wanted to determine whether there are points of exact order 100 of
degree 100, and were factoring the exact-100-div.pol. to investigate
this.

My first idea is to look more at the exact 4- and 25-division polys,
since any point of order 100 will be a sum of points of orders 4 and
25, and of course they have smaller degree.  And the 2- and 5-
div.pols. should also not be ignored.  For example, if P has order 100
and degree 100 then 50*P has order 2 and degree dividing 100, which
implies that E has a rational point of order 2.  So for a start only
look at curves with some rational 2-torsion.  I'm sure that you can
come up with many other similar necessary conditions, that is just the
simplest.

Secondly, I would look at the polynomials whose roots correspond to
m-isogenies.  These are harder to come by but obviously have smaller
degree, and give you relevant information.  For example it seems
likely that a degree 100-factor of the exact 100-div.poly will be
associated with a (cyclic) 100-isogeny defined over an extension of
degree 5 (since phi(100/2=20=100/5), though I don't think that's an if
and only if.  And specifying a cyclic 100-isogeny is equivalent to
specifying a pair of cyclic isogenies of degrees 4 and 25 which will
again be easier to get hold of.

Just some thoughts, not a complete solution.

John

On 14 June 2013 12:10, Richard in Reading
<richard_in_reading@yahoo.co.uk> wrote:
> Thanks for your reply to the list. I'm sorry I was sloppy in explaining what I was factoring.
>
> In this particular instance I was trying to factor the polynomial whose roots are the x-coordinates of exact order 100 as you mention in your second point. I had already removed all the factors in common with the division polynomials corresponding with divisors of 100.
>
> For example, on the curve "496a1", elldivpol(e,100) yields a polynomial of degree 5001.
> Removing all the factors in common with lower division polynomials leaves a polynomial of degree 3600 which apparently can't be factored.
>
> For the curve "1584s1" however, the corresponding polynomial of degree 3600 factors into six polynomials of degree 100,100,200,200,1000,2000
> and it's the polynomials of degree 100 which I'm interested in.
>
> I believe that your step 3 would be broadly equivalent to evaluating the 100th term of the relevant elliptic divisibility sequence. Unfortunately I believe it would be equivalent to evaluating the polynomial of degree 3600 and then I'd have to factor the result. I really want the results of evaluating the polynomials of degree 100.
>
> I would be very grateful for your thoughts now that I have clarified my situation.
>
> Thanks!
>
> Richard Heylen