# 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.

-
My understanding is that there is no known algorithm which is guaranteed to find the rational points on an elliptic curve. Section 4.2 of Poonen's survey www-math.mit.edu/~poonen/papers/millennial.pdf briefly discusses what is known and has references. –  Qiaochu Yuan Oct 13 '10 at 14:22
Qiaochu, you are right in principle. But if one is only interested in the practical matter of finding points, rather than the well-foundedness of the methods, then there are algorithms. More precisely, if you believe the Birch and Swinnerton-Dyer conjecture, then there are efficient algorithms that are guaranteed to terminate. The analytic rank (which is computable in practice) will tell you how many points you need to find and the regulator (on which you get a bound from the leading coefficient of the L-function at s=1) will tell you where to look for them, i.e. will give you height bounds. –  Alex B. Oct 13 '10 at 15:15
My answer to this question was non-sense, as kindly pointed out by Chris Wuthrich, so I deleted it, lest people get confused. I was talking about modular symbols, which were used by Cremona to generate his database of elliptic curves, but this has nothing to do with the present question. Sorry about that, I should stop posting so late at night! –  Alex B. Oct 13 '10 at 17:45

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.

-
Regarding "Sage over the standalone version of mwrank": In fact, Cremona has even deprecated the standalone version. See the note here: warwick.ac.uk/~masgaj/mwrank Also, it is worth mentioning Denis Simon's algebraic 2-descent code, which is also in Sage, and can be fast in certain case. –  William Stein Nov 20 '10 at 21:14
A late postscript to comment on William Stein's comment. The only thing deprecated is my distribution of mwrank independently, either as source code or as a binary, since the source code is 100% included in Sage's distribution, and to run it when you have Sage is as simple as typing "sage -mwrank" if you want to. This makes life simpler for me, which his a good thing (at least for me). I still use mwrank stand-alone myself (hardly surprising). Secondly, Jamie's remark about mwrank in Sage being more up to date is simply nonsensical. –  John Cremona Feb 4 '12 at 17:37
Thanks for clarifying that John. I'm sorry was confused about that. –  Jamie Weigandt Jul 5 '12 at 19:10

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 beginner would be much better off starting off with "Rational Points on Elliptic Curves" by Silverman and Tate (aka Tate's Haverford Lectures). –  Victor Miller Oct 14 '10 at 1:32
Having seen many beginners learn about the descent algorithm, both from the perspective of Silverman-Tate and Galois cohomology, I think it's probably better for even a beginner to just learn Galois cohomology and learn descent the right way. All the notation and equations in the presentation in Silverman-Tate really obscure what is going on, in my experience. –  William Stein Nov 20 '10 at 21:37

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

-
I agree best with this answer. The descents (as in Robin's answer) tell us that in order to find rational points on an elliptic curve, we better search on one of its torsors. But in the end, we have to do some "brutal search" and that is where the crucial improvements in ratpoints are useful. ... and the only other known method to find rational points is by modularity, say by using Heegner points or variants of them, or (as Pollack and Kurihara do) using supersingular Iwasawa theory. But all of them only work when the analytic rank is 1. –  Chris Wuthrich Oct 13 '10 at 17:01
Finally one should add that it is easy to find the torsion points, if there are any. Most of this is implemented in magma and lots of it in sage. –  Chris Wuthrich Oct 13 '10 at 17:02
A very recent version of ratpoints is in Sage. Inputing "import sage.libs.ratpoints as r; r.ratpoints([46224, -3024, 0, 1], 200)" will output lots of points on the curve $y^2 = x^3 - 3024x + 46224$, such as [(1, 0, 0), (-60, 108, 1), (-60, -108, 1), (-32, 332, 1), ...] –  William Stein Nov 20 '10 at 21:20
Here's an example of finding a point on a rank one curve in Sage using Heegner points: "E = EllipticCurve('37a'); P = E.heegner_point(-7); P.point_exact()". The rank 1 curve $y^2=x^3+7823$ provides a spectacular example in which Heegner points fail in practice, but doing a FOUR descent succeeds. Michael Stoll wrote a paper about this, but I can't find it online anymore (it vanished from his website), so here is a temporary link: wstein.org/home/wstein/tmp/4-descent.pdf Also, having read the ancient Peter Green Heegner points program you link above, I do not recommend it. –  William Stein Nov 20 '10 at 21:28

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.

-
To compute generators of the Mordell-Weil group of $y^2+a_1xy + a_3 y = x^3 + a_2 x^2 + a_4 x + a_6$, type EllipticCurve([a1,a2,a3,a4,a6]).gens(). If you type print(EllipticCurve([a1,a2,a3,a4,a6]).mwrank()), then you'll see what mwrank did. For more about elliptic curves over the rationals in Sage, see this page: sagemath.org/doc/reference/sage/schemes/elliptic_curves/… –  William Stein Nov 20 '10 at 21:16

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.

-
Charles, there are deterministic algorithms. They often rely on unproven conjectures, but they happen to work very well in practice. Also, probabilistic algorithms are referred to as "algorithms", just as deterministic ones, and I don't quite see what is misleading about this terminology. –  Alex B. Oct 13 '10 at 15:18
You haven't heard the one about showing Birch-Swinnerton-Dyer unprovable by showing the rank is not computable? Of course it is misleading here to mix up different kinds of algorithms. Brute force search will find a rational point on a curve if it is exists (partial correctness). A correct algorithm is what people generally mean by something being "algorithmic". A good probabilistic algorithm is typically what is sought in computational number theory, and a good algorithm with correctness proof conditional on some known conjecture is of real interest. –  Charles Matthews Oct 13 '10 at 15:52
"You haven't heard the one about showing Birch-Swinnerton-Dyer unprovable by showing the rank is not computable?" Huh???! What the heck are you talking about? Assuming rank(E)<=1 or Sha(E)[p^oo] finite for one p, or BSD rank is true, then there is a deterministic algorithm to compute E(Q). Without making one of those assumptions, we still don't know. –  William Stein Nov 20 '10 at 21:33
It was something Manin included in an old paper in Russian Mathematical Surveys. Attributed to Shafarevich, if I recall correctly. Manin said "if this is a joke, it is a gloomy one", or suchlike. –  Charles Matthews Nov 21 '10 at 8:49

Hi,I am a amateur mathematician.I can't understand what ı did exactly but here ı seek some solutions of that equation.I don't use LaTeX etc.(sorry)So ı saw that congruent numbers subject on wikipedia.I checked the text and ı saw that finding rational points means showing rank is positive and the equation y^2=x^3-xn^2.First ı worked on it.y^2/x=x^2-n^2 than x^2=n^2+y^2/x than if y^2=a^2/x so x^2=n^2+A^2/x^2 that reminds Pythagoras triplets.For exp. if x^2=25 than n^2=9 so A^2=20^2 ,y=20^2/5.This was the first thing ı did.Another thing was to search general solution about y^2=x^3+ax+b.Firstly ı used y^2=x^3 transformation.Than x^3-b=x^3+ax than -b=ax must be true.So x=-b/a so if -b,a=n^2 than this equation can be true.So for exp. y^2=x^3+9x-4 must be true for values of y=-2^3/3^3 and x=-2^2/3^2.I think ı can find another ways.

-
These are good first steps. However, the question is about automating the search for solutions by computer. It appears that you need to do some more work, beyond what you have written, before you have an algorithm. –  S. Carnahan Feb 9 '13 at 8:19