How to compute rational or integer points on elliptic curves

This is an attempt to get someone to write a canonical answer, as discussed in this meta thread. We often have people come to us asking for solutions to a diophantine equation which, after some clever manipulation, can be turned into finding rational or integer points on an elliptic curve. See here, here, here, here, here. (This list is biased towards questions I have answered because I remember them best; other people have answered such questions as well.) I would like an answer to which, after one of us has explained the cleverness, we could direct the OP.

• How to find both rational and integer solutions

• Good software solutions. Ideally, it would nice to have a walkthrough for doing these things with Sage Notebook, so that people could find solutions without even installing anything.

• References for how to transform some standard presentations of elliptic curves into Weierstrass form, so that we don't have to write out the algebra every time. I'm thinking of a cubic in $\mathbb{P}^2$ with a rational point that is not a flex, $y^2 = \mbox{degree 4 polynomial}$, a $(1,1)$ curve on $\mathbb{P}^1 \times \mathbb{P}^1$, or an intersection of two quadrics in $\mathbb{P}^3$.

-
Is there an algorithm for finding all the integer points on an elliptic curve? – i. m. soloveichik Sep 27 '12 at 14:51
Perhaps make this thread community wiki? Several answerers can address the 3 different points, as I imagine one giant answer from one author would be harder to do. – Ragib Zaman Sep 27 '12 at 14:55
@i.m.soloveichik Both in practice and theory, yes. In theory, yes by a result of Baker; see math.stackexchange.com/a/32903/448 . In practice, there are algorithms in SAGE and MAGMA. These are not the same algorithm; my understanding is that the actually implemented methods are correct if they terminate but are not guaranteed to terminate. – David Speyer Sep 27 '12 at 14:57
@RagibZaman Maybe. I had planned to put a bounty on this, because giving a good answer to this deserves a lot of rep. Can I give bounties on CW answers? (I'd be glad to give bounties to multiple users, as appropriate.) – David Speyer Sep 27 '12 at 14:58
Added (reference-request) in light of the last paragraph. – zyx Oct 14 '12 at 7:48

The question is rather broad, but here are some references.

Formulas for Weierstrass equation from a plane cubic, $y^2=$ quartic, intersection of two quadrics and some other cases, can be found in Chapter 1 of Ian Connell's Elliptic Curve Handbook .

The $\tt{mwrank}$ algorithm is described in Cremona's book Algorithms for Modular Elliptic Curves. The documentation of this and other routines in Sage for elliptic curves over Q is at http://sagemath.org/doc/reference/sage/schemes/elliptic_curves/ell_rational_field.html.

Connell's ECH chapter 3.6 is on methods for computing Mordell-Weil bases.

Theory and practice for rigorously finding all integer points:

Stroeker & De Weger Solving elliptic diophantine equations: the general cubic case (1999)

Stroeker & Tzanakis, Computing all integer solutions of a genus 1 equation (2003)

The rational and integer point-finding questions have been asked several times on Math Overflow, with references and some code provided. Some answers are directly from the software developers.

http://mathoverflow.net/questions/42016/algorithms-for-finding-rational-points-on-an-elliptic-curve

http://mathoverflow.net/search?q=mwrank

Sage code and references (integral points):

http://mathoverflow.net/questions/6676/integer-points-of-an-elliptic-curve

http://mathoverflow.net/questions/7907/how-to-find-all-integer-points-on-an-elliptic-curve

Sage code (rational points):

http://mathoverflow.net/questions/57498/looking-up-the-mordell-weil-rank-and-generators-of-a-weierstrass-equation/57502#57502

Other items of note -

1. All the current algorithms for computing the Mordell Weil group are conditional on conjectures such as BSD or the finiteness of Sha.

2. Some of the software routines take as input a general Weierstrass model $Y^2 + a_1 XY + a_3 Y = X^3 + a_2 X^2 + a_4 X + a_6$, not the rational Weierstrass form $y^2 = x^3 + Ax + B$. The latter would be entered as $(a_1,a_2,a_3,a_4,a_6) = (0,0,0,A,B)$.

-