The following should be of interest to David Harvey, David Kohel, Chris Wuthrich and WIlliam Stein (at least!).
Following from my reviewing of Chris's #3377 (torsion subgroups of elliptic curves over number fields) where I found a bug (see #3383) in William's new full_division_polynomial() code (see #3109): The bug was caused by some horrendous Grobner basis reduction in a 2-variable polynomial ring over a number field. I was able to eliminate it by reworking William's full_division_polynomial() to work in the genuine function field of the curve. Thus, if K is the base_ring of the curve I construct in order the polynomial ring K[x], then its field of fractions K(x), then -- via the polynomial ring K(x)[Y] -- the field K(x)(y) where y^2=polynomial in x is the equation of the curve. (I am currently assuming that the curve is in short Weierstrass form as WIlliam did, though that wilkl be fixed in due course). Elements g of that field have two components g[0] and g[1], both rational functions in x, representing g[0]+y*g[1]. It is possible though slightly awkward to evaluate such a function g at a point P. What works is lift(g).subs(Y=P[1]).subs(x=P[0]) Now full_division_polynomial(m) returns an element g of that field, which if m is odd happens to be a polynomial in x (no denominator, no y term, i.e. g[1]==0) and if m is even happens to be y times a poly on x (no denominator and g[0]==0). Using that I reworked multiplication_by_m() as necessary and hence division_points(). doctests all pass, and the example which previously failed in #3383 now passes. Problem 1: Over Q, multiplication_by_m(10) takes ages -- over 3 minutes! -- even with the x_only=True option. The time is almost all spent in dividing one element of QQ(x) by another. That is just a simple division of two rational functions (polynomials of degrees 99 and 100 with no common factor) -- possibly the time is taken computing their gcd? I know that ZZ[x] operations are faster than QQ[x] but it would be very ugly to try to detect this special case since the code is otherwise generic and works over any field (char. not 2 or 3 until we stop using short W. equations). Problem/question 2: looking at the code in ell_generic.py I find that there are now *3* different implementations of division polys of various kinds. (1) E.division_pol = E.torsion_pol is by David Kohel (2005-04-25) and returns a polynomial in x alone, with a factor of the 2-division poly in x when m is even. (2) E.full_division_pol is William's new code (which can be asked to call the preceding when m is odd) which returns a polynomial in x and y, i.e. in the 2-variable poly ring over K, which happens to be of the form p(x) or y*p(x) where p is a poly in x alone (but belonging to K[x,y]). (3) There is code which is all commented out due to David Harvey (2006-09-24) consisting of 3 functions pseudo_torsion_polynomial(), multiple_x_numerator(() and multiple_x_denominator(). The first is the same as before for odd m but for even m just omits the factor of the 2-division poly. I like this implementation: it uses a cache, and also the user supplies their own 'x' which need not be an indeterminate. This is *very* useful since it is expensive to compute (say) the 10th division poly as a polynomial and then substitute avalue for x, it is much faster to evaluate as you go along. The last two give the numerator and denominator of the x-coordinate of m*P, i.e. of the first rational function returned by William's multiplication_by_m(). [By the way, it is easy to get the y-coordinate from the x-coordinate: if the x-coord is X(x) then the y-coord is c*y*X'(x) where c is a constant. I think the constant is m in this case (look at the invariant differential). Does anyone know why those three functions are commented out? William, why did you write your own new functions instead of using these? Can we try to clean all this up once and for all? Would you trust me to do this? John --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
