What is the complexity of finding an integral point on an elliptic curve?

Question

Let $E$ be an elliptic curve over rational numbers. We know that the set of integral points on $E$ is finite. What is the complexity of finding a point $P\in E(\mathbb{Z})$?

Indeed I'm trying to find integral points on an elliptic curve of the form $y^2=x^3+ax^2+bx$, if the rank is $1$, I can use Silverman's algorithm in $$COMPUTING~RATIONAL~POINTS~ON~RANK~1~ELLIPTIC~CURVES~VIA~l-SERIES~AND~CANONICAL~HEIGHTS$$ Because I know P is it's generator! But the conductor of $E$ and logarithmic height of $P$ are too large. Is there an efficient algorithm to find $P$?What is the best algortihm in the cases where $rank(E)>1$?

Answer 1

The best unconditional complexity bounds I know of are those coming from Baker's theory of linear forms in logarithms. Baker wrote a paper "The Diophantine equation $Y^2 = aX^3 + bX^2 + cX + d$" where he worked out some impractical but rigorous bound on the complexity of enumerating the integral points on an elliptic curve. I think that there better results on linear forms in logarithms that can improve this bound, hopefully someone will surface that can address this.

In practice, you almost never use Baker's method for computing integral points on elliptic curves. Usually one computes a basis for the Mordell-Weil group first and then uses the GPZ algorithm to enumerate the integral points. (See William Stein's answer in joro's first link for a description of the various implementations of this.) There should be some improvement in the complexity of GPZ coming from new results on linear forms in elliptic logarithms, but I'm not sure if anyone has really worked this out in detail.

The main problem with the GPZ approach is computing a Mordell-Weil basis in the first place. There is no algorithm for determining a basis for the Mordell-Weil group which has been unconditionally proven to terminate with the correct answer. This is a central problem related to BSD and the finiteness of Sha. It's also the main bottleneck in using GPZ to get a much better bound on the complexity the OP asked about.

There are conditional algorithms that assume finiteness of Sha, or the BSD rank conjecture. Assuming GRH usually helps speed up finding upper bounds on the rank in both cases. For rank at least $2$, we don't have a great way of finding rational points like the Heegner point construction for rank $1$. Hindry wrote a great paper about why computing the Mordell-Weil group is hard, and it's probably about the best place to get an idea of the complexity without getting the experience of computing a bunch of Mordell-Weil groups.

I'm pretty clueless about what the true complexity of computing the Mordell-Weil rank should be. It's somewhere between "not much easier than determining the number of prime factors of the conductor" and "not computable". Of course these are both extremes, the complexity is probably closer to $N^{1/2 + \epsilon}$ where $N$ is the conductor.

Computing ranks is still an art form. If you have a particular curve $E$ in mind, and you've tried E.gens() in Sage, MordellWeilShaInformation(E) in Magma, and looked for it at http://www.lmfdb.org, then it would be good to ask someone.