I am looking for algorithms on how to find rational points on an [elliptic curve](http://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/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.



Algorithms for finding rational points on an elliptic curve?
A good reference to get started from the algorithmic point of view is Chapter 3 of Cremona's [*Algorithms for Modular Elliptic Curves*](http://www.warwick.ac.uk/~masgaj/book/fulltext/index.html). 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](http://www.warwick.ac.uk/~masgaj/papers/index.html). 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](http://www.warwick.ac.uk/~masgaj/papers/index.html).


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.


