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.