I attach some Pari code which computes various things, including Nagell's algorithm, including forward and reverse transforms. Accompanying it is some test code which attempts to verify that the inverse transform does what it is supposed to, i.e. it composes with the forward transform to give the identity. In various versions of Pari, the test will fail, due to bugs in Pari, but hopefully it passes on the latest version.
There's all sorts of other stuff in that file, some of which is hopelessly inefficient, but which was purpose written and did not need to be fast. Of course Nagel's algorithm should not take minutes, ever. I don't make any guarantees that this code is useful for anything, even the purpose discussed here and it comes with no warranty whatsoever, but the code is hereby released under GPL v2 or above if it proves useful to anyone. Here is a link to the code: http://sage.math.washington.edu/home/wbhart/PicardBasis.txt The functions you want are toEllipticCurve and testNagell. The function toEllipticCurve(C, P) takes as arguments a cubic curve C and a Qp-rational point on it. A stupidly naive function for finding such a point is given by the function QpPoint(C, p) where p is a prime. This function will also fail in various versions of Pari, but should be fine in the latest version. The function would have to be modified if you don't want to work with Qp, but it should be straightforward to modify it. The hard part is getting all the transformations right, and they are there. Note the line: u;v;sqrtdelta;x;y;tau;t;ud;vd;wd;Ud;Vd;Wd;U;V;W;w; at the top of the file is **absolutely essential** to the correct operation of the Nagell algorithm Bill. On 23 May, 02:44, "Bobby Moretti" <[EMAIL PROTECTED]> wrote: > Andrey, > > The bundle probably would not be of much use to you, since the > function takes as input a Sage multivariate polynomial ring element > and outputs a Sage elliptic curve over some field, when all you want > is symbolic expression in Weierstrass normal form. > > Do you have a copy of the implementation of Nagell's algorithm that > you were using? I'm curious as to what is taking so long, since there > aren't very many complicated steps; it's mostly basic arithmetic. > > -Bobby > > > > On Thu, May 22, 2008 at 1:11 PM, William Stein <[EMAIL PROTECTED]> wrote: > > Andrey, > > > Check out the hg bundle attached to this ticket: > > http://trac.sagemath.org/sage_trac/ticket/1136 > > > Bobby Moretti was implementing code for doing this transformation, but > > never finished due to a subtle bug in the transformation maps (he gets the > > right cubic but not the right maps). It's possible you'll find the above > > bundle > > useful (no clue). > > > On Thu, May 22, 2008 at 1:04 PM, Andrey Novoseltsev <[EMAIL PROTECTED]> > > wrote: > > >> I tried to convert > >> 2*x*y^2 + 2*a5*t*x*y - x^2 + (2*a4 - 8*t^3)*x - 1, > >> where a4, a5, and t are some complex parameters (which I would like to > >> keep as undetermined parameters), to Weierstrass normal form using > >> Nagell's algorithm and was not quite successful since some steps near > >> the end do not finish in a reasonable time (i.e. a few minutes). It is > >> possible that I have done some mistakes, since I didn't really tested > >> my code yet, but Jacob Lewis told me that this algorithm isn't very > >> fast anyway. > > >> As far as I can tell, Sage can do this conversion using MAGMA, but > >> only over rational field. Can anyone recommend an efficient way of > >> doing such a conversion with symbolic coefficients? Or, perhaps, it is > >> already done and I just cannot find the proper function? > > >> Thank you! > >> Andrey > > > -- > > William Stein > > Associate Professor of Mathematics > > University of Washington > >http://wstein.org > > -- > Bobby Moretti > [EMAIL PROTECTED] > > -- > Bobby Moretti > [EMAIL PROTECTED] --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com 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 -~----------~----~----~----~------~----~------~--~---
