Algorithms for finding rational points on an elliptic curve? I am looking for algorithms on how to find rational points on an elliptic curve $$y^2 = x^3 + a x + b$$ where $a$ and $b$ are integers. Any sort of ideas on how to proceed are welcome. For example, how to find solutions in which the numerators and denominators are bounded, or how to find solutions with a randomized algorithm. Anything better than brute force is interesting.
Background: a student worked on the Mordell-Weil theorem and illustrated it on some simple examples of elliptic curves. She looked for rational points by brute force (I really mean brute, by enumerating all possibilities and trying them). As a continuation of the project she is now interested in smarter algorithms for finding rational points. A cursory search on Math Reviews did not find much.
 A: The best practical solution is to have someone else do the work.  You can look up the curve in Cremona's tables, if it is not too large. If it is larger than that, you can use mwrank, a free standing C++ program. I believe that SAGE and MAGMA also both have this functionality, although I couldn't find the syntax in a quick search.
A: It is misleading to say "algorithm", really. There are probabilistic algorithms, and then hard cases (evidence of a point of infinite order that is hard to find). See for example http://www.jstor.org/pss/2152939 . I think of Andrew Bremner as one of the experts on the highly numerical side, and you should add his name to John Cremona's.
A: There is a whole industry devoted to this. The basic method is by
descent, which is a formalized version of the infinite descent proofs
of Fermat and Euler. It helps if there are rational 2-torsion points
but it's not essential. Chapter X in Silverman's The Arithmetic of Elliptic
Curves is called "Computing the Mordell-Weil group". It has lots of good
information, but maybe isn't so easy for a beginner due to its heavy use of
group cohomology.
A: There are clever ways of speeding the brute force enumeration. An implementation of such is M. Stoll's ratpoints program:
http://www.mathe2.uni-bayreuth.de/stoll/programs/index.html
A completely different way of generating points on elliptic curves is to use Heegner points, but it only works when the rank is one. This is technically more sophisticated but I believe there are also implementations. Google yields:
http://www.math.mcgill.ca/darmon/programs/programs.html
A: A good reference to get started from the algorithmic point of view is Chapter 3 of Cremona's Algorithms for Modular Elliptic Curves. It contains a good deal of pseudocode which explains how Cremona's C++ package mwrank computes rational points on elliptic curves.
Some of the more intricate details, such as second descents are left to Cremona's papers here. Given an elliptic curve with coefficients that aren't too big, your best bet to quickly find the points you're looking for will probably be to use mwrank as included in Sage.
As has been explained to me in the comments. Sage is not the only way to get access to mwrank and the other programs that make up Cremona's elliptic curve library (eclib), but it is arguably the easiest way to get it, and it contains much more elliptic curve functionality, such as the method E.analytic_rank() which if run on elliptic curve of reasonably sized conductor, will return an integer that is proBably the analytic rank of the curve.
