Let $E$ be an elliptic curve over $\mathbb{Q}$ and $E(\mathbb{Q})[2]=\{o,T\_1,T\_2,T\_3\}$. Let $P=2R$ be a point in $2E(\mathbb{Q})$, using $2$-division polynomial, we can compute $1/2P$, but it gives the set $\{R,R+T\_1,R+T\_2,R+T\_3\}$. How can find $R$ in this set? In other word, is there an algorithm for point halving in $E(\mathbb{Q})$?Indeed I have $S\_1$ and I know there exists $k\in\mathbb{N}$ such that $P=2kS\_1$, I need to know $kS\_1$.



Point halving on elliptic curves over $\mathbb{Q}$
To some extent, it depends on the magnitude of the numbers involved. But when you say that you "know" $P$, I assume that means that you can write down the coordinates of $P$ as rational numbers. So there may be hundreds, or even thousands, of digits in the numerators and denominators of the coordinates of $P$, but not (say) $2^{80}$ digits. (This will mean that $k$ isn't all that large, of course, so you can just compute $2mS\_1$ for $m=1,2,\ldots$.) Anyway, instead of using heights, you can write use an isomorphism 
$$z:E(\mathbb{C})\xrightarrow{\;\sim\;}\mathbb{C}/(\mathbb{Z}+\mathbb{Z}\tau),$$ 
where you compute $\tau$ and the $z$-values of $P$ and $S\_1$ to several thousand digits. Then you're looking for integers $k$, $n\_1$, and $n\_2$ that solve
$$ z(P) - 2kz(S\_1) + n\_1 + n\_2\tau = 0, $$
and there are standard lattice reduction methods that should do the trick. This should work even if $k$ gets fairly large if you use enough digits of precision on the map $z$.


On the other hand, if it is not possible to explicitly write down the points $P$ and $S\_1$, then you need to explain what you mean when you say that you know these points.


