John Cremona on Mon, 17 Jun 2013 10:21:45 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: Calculate lower degree factors of elldivpol(e,100) |
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