# Algorithm for finding integral points $P,n P$ on an elliptic curve

We found and implemented algorithm which finds integral points of infinite order $$P=(X_1,Y_1)$$ and $$nP=(X_2,Y_2),n>1$$ on an elliptic curve $$E : y^2=x^3+a_4 x + a_6$$.

Let $$X(x)/Z(x)$$ be the $$X$$ coordinate of the multiplication by $$n$$ map on $$E$$. $$X,Z$$ are polynomials in $$x$$.

By the integrality of $$P,n P$$ we have $$X_2=X(X_1)/Z(X_1)$$ and $$Z(X_1) \mid X(X_1) \iff \gcd(Z(X_1),X(X_1))=Z(X_1)$$.

Let $$r$$ be the resultant of $$X$$ and $$Z$$. The gcd of $$X(x),Z(x)$$ at integers is divisor of $$r$$. For all divisors $$d$$ of $$r$$, check if the root of $$Z(x)=d$$ is $$X_1$$ and it is on the curve.

So this algorithm finds all integral pairs $$P,n P$$ on $$E$$.

The complexity is the maximum of factoring the resultant and iterating over its divisors.

Scaling rationals to integers: If $$(x/u,y/u)$$ is on $$E$$, then this give rise to integral point on $$y^2=x^3 + a_4 u^4 x + a_6 u^6$$.

Over the rationals, assume $$P=(x_1/z_1,y_1/z_1)$$ is rational point and $$2P=(x_2/z_2,y_2/z_2)$$. If we guess a multiple of $$z_1 z_2$$ : $$u= C z_1 z_2$$, work on the isomorphic curve $$E'=x^3+a_4 x u^4 + a_6 u^6$$. $$E'$$ will have the integral points $$P'=(u^2 x_1,u^3 y_1)$$ and $$2P'=(u^2 x_2,u^3 y_2)$$. The algorithm will find the integral points $$(X_1,Y_1)$$,$$(X_2,Y_2)$$ on $$E'$$ and this will find rational points on $$E$$,$$(X_1/u^2,Y_1/u^3)$$ and $$(X_2/u^2,Y_2/u^3)$$. Observe that we need not know $$z_1,z_2$$, just a multiple of their product.

So the algorithm finds rational points of infinite order at the cost of guessing multiple of $$z_1 z_2$$ and this is efficient if $$z_1 z_2$$ is smooth, i.e. product of small primes.

Q1 Is this algorithm known?

We get experimental support, e.g.:

sage: k0=57;E=EllipticCurve(QQ,[0,k0^3]);pts=jorointegral1(E);pts
(-38 : 361 : 1), (112 : 1261 : 1), (456 : 9747 : 1)]


Comment claims that curves for which the algorithm works are rare. We believe this is not true, because for all $$E$$ of positive rank, there exists isomorphic $$E'$$ with $$P,nP$$ integral of infinite order. This can be used if the denominators $$z,z_2$$ are smooth.

• I fear it is rather rare to find an $n>1$ and $P$ such that $P$ and $nP$ are integral points of infinite order on an elliptic curve. Torsion points can be found easier than that. Also $r$ is linked to the discriminant of $E$, in fact the method for $n=2$ is what is used in the proof of the theorem of Lutz-Nagell. Jun 17 '21 at 14:51
• @ChrisWuthrich No, it is not rare for points of infinite order. I edited with example.
– joro
Jun 17 '21 at 15:21
• @ChrisWuthrich By scaling rationals to integers, for all E there is isomorphic E' with two integral point P,nP. This can be used if the denominators are smooth.
– joro
Jun 17 '21 at 15:36
• @joro When dealing with average questions for elliptic curves over $\mathbb{Q}$, it is standard to represent them by equations $y^2=x^3+Ax+B$ which are quasi-minimal, i.e. $p^4 | A \Rightarrow p^6 \nmid B$ (such an equation is unique). Then you order them by naïve height and try to compute the density. It seems that what you are doing is counting equations, not elliptic curves. Jun 17 '21 at 17:17
• @joro Sure you can rescale the equation to make any pair of points integral. But then there is no point in your algorithm as you'll know the answer already. For a given, say quasi-minimal equation the set of $n>1$ with integral points $P$ and $nP$ is small if not empty. Jun 17 '21 at 19:16

Rational points which are hard to find are those of large height, and in particular large denominator. This method will only find rational points with denominator u when you scale the equations by u, which requires knowing u in advance or looping over all possible u. Try this curve: https://www.lmfdb.org/EllipticCurve/Q/294504803/d/1

• Thanks, I didn't claim the algorithm is universal. And many thanks for making mwrank open source.
– joro
Jun 18 '21 at 11:09

For what it's worth, it should not be possible to make $$P$$ and $$nP$$ integral on a quasi-minimal equation if $$n$$ is very large. More precisely, the following theorem holds. It quantifies what Chris Wuthrich said in the comments.

Theorem: If Lang's height conjecture is true (or if the $$ABC$$-conjecture is true), then there is an absolute constant $$C$$ such if $$E/\mathbb Q$$ is an elliptic curve given by a quasi-minimal Weierstrass equation, $$E: y^2 = x^3 + Ax + B,\quad \text{A,B\in\mathbb Z, \gcd(A^3,B^2) 12th power free,}$$ and if $$P\in E(\mathbb Q)$$ is a point of infinite order, then $$P\in E(\mathbb Z) \quad\text{and}\quad nP \in E(\mathbb Z) \quad\Longrightarrow\quad n \le C.$$

• Thanks. I suppose you assume infinite order of the point.
– joro
Jun 18 '21 at 11:32
• @joro Yes, infinite order. Clearly trivially false otherwise! I edited the answer. Jun 18 '21 at 11:48
• Your constraints on A,B are exactly the opposite of what I do on purpose. Large gcd of A,B on E' helps me to find rational point on the minimal model E with large denominator.
– joro
Jun 18 '21 at 14:44
• If you want to use non-minimal models, then it's easy (as you've indicated) to get $P$ and $nP$ integral for an arbitrarily large $n$ simply by clearing denominators. This can be done quantitatively in the sense that the denominator of $nP$ grows roughly like $\exp(n^2\hat h(P))$, so the number of digits grows quadratically with $n$. More generally, if $P_1,\ldots,P_r\in E(\mathbb Q)$ are independent points, then one can ask for the smallest $D$ that clears all of their denominators. This is in the literature, but in any case not hard to do using canonical heights. Jun 18 '21 at 15:53