# Time complexity of finding a point of infinite order on a rank 1 elliptic curve over Q

As an outsider, it sounds like a lot of progress has been made on understanding rank 1 elliptic curves over Q. Much of the BSD conjecture is known for rank 1, and Heegner points provide a way in principle to calculate a rational point of infinite order on the curve. However, it is unclear to me what properties are feasible to obtain computationally.

So I would like to know, given an elliptic curve in minimal Weierstrass form, and assuming the factors of the discriminant and other invariants are known (to sidestep possible issues getting into the complexity of factoring), can we efficiently calculate a point of infinite order on the curve? What is the time complexity of currently known methods?

Does the answer change if we restrict to some special subsets of elliptic curves, such as Mordell curves $$y^2 = x^3 + k$$? Or even restricted further to Mordell curves with $$|k|>1$$ and square-free, where it is known that all points are of infinite order?

• Hey super fast comment: it’s expected that the number of digits required to write down the x-coordinate of a generator will be about k^{1/2} (this follows from Gross-Zagier plus conjectures about the size of Sha and the L value). So just writing down the answer will take \Omega(k^{1/2 - \eps}) time! – alpoge Feb 26 at 5:59