what is complexity of finding a non-torsion point on elliptic curve

Question

Let E be an elliptic curve over $Q$ with positive rank $r$. I am looking for algorithms which find a rational point on $E$. I think the algorithms find points with the lowest height. But when I use Magma to find the generators of the elliptic curve $y^2 = x^3 - 1563056672958141*x$ (which has rank 2, with generators P1=[48408867,194361588954] and P2=[48432972,194700535386]), Magma returns $Q=[260509445493025,-4204701905638250451710]$. I know $\hat{h}(Q)>\hat{h}(P1),\hat{h}(P2)$!My question is: finding a rational point on E is easier than finding its generators?

Answer 1

There are two questions. First, how does one find some points of infinite order? One can simply search (using congruences to narrow the search space a bit). It is often more efficient to search for points on homogeneous spaces of small degree, say 2 or 3. This is equivalent to doing a 2 or 3 descent. This is all explained very clearly in Cremona's book. I expect that this is what is being done in Sage. These sorts of search algorithms do not necessarily give generators, but if one is lucky, they give a set of points that has the correct rank.

For the rank 1 case, there are at least two other ways to find a point of infinite order. One is to compute a Heegner point explicitly to many decimal places, and then recognize the rational numbers that form its coordinates. This was suggested by Zagier, and he shows that it can be quite practical. The second is to compute the $L$-value $L(E,1)$ to many decimal places, use that to get a handful of values for $\hat h(P)$, and use the value of $\hat h$ to limit the search for $P$. This is described in a paper of mine in Math Comp.

Okay, now let's suppose that you have independent points $P_1,\ldots,P_r$ and you want to find generators for their divisible hull in $E(\mathbb Q)$. So we're looking for points $Q$ and integers $m$ such that $$ mQ \in \text{Span}(P_1,\ldots,P_r),\quad\text{but}\quad nQ \notin \text{Span}(P_1,\ldots,P_r)\quad\text{for $n\lt m$.} $$ Consider first the easiest case of rank 1, and let $P=P_1$. Using the addition formula, it's easy to check if $P=mQ$ with $Q\in E(\mathbb{Q})$ for small values of $m$, say for $2\le m\lt 10$. If you find a smaller point, then you can repeat the process. If not, then you know that if $P=mQ$, then $m\ge 10$, so $$ \hat h(Q) = \frac{1}{m^2}\hat h(P) \le \frac{1}{100}\hat h(P). $$ (There are algorithms to compute canonical heights.) In any practical situation, one should be able to check enough $m$'s to ensure that $\hat h(Q)\le 1$, say. Then standard estimates for the difference between $\hat h(Q)$ and $h(x(Q))$ will give a feasible search space if the coefficients of $E$ aren't too large.

The general case is similar. I'll illustrate for $r=2$. If the span of $P_1,P_2$ is divisible by $m$, then we can find a rational point $Q$ satisfying $$ mQ = a_1P_1+a_2P_2\quad\text{with $0\le a_1,a_2\lt m$.} $$ So for each $m$, one needs to check $m^2$ points for divisibility. Do this for (say) $m<10$. If you find no points, then you can assume that $m\ge 10$. In that case, $\hat h(Q)$ can again be bounded in terms of the height regulator of $\text{Span}(P_1,P_2)$, which in turn will (with any luck) give a reasonable brute force search space for possible $Q$'s.

Answer 2

The question is not so well-posed, as Alex B. notes. But that aside, assuming we do have an elliptic curve over $\mathbb{Q}$ of rank $\ge 1$ then if you can find one of the generators (or \emph{the} generator if the rank is $1$) of the subgroup of points of infinite order then you have also found a points of infinite order. However, if you have a point infinite order -- which is trivial to check by calculating a finite set of multiples of the points (by Mazur's theorem) -- then you might not be able to decide if it is a generator.

So, in that sense determining if a point is a generator is more difficult than determining if it is of infinite order.

Maybe that is what you meant?