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$.

6$\begingroup$ How are you supposed to identify $R$? $\endgroup$– Felipe VolochOct 8, 2013 at 13:13

$\begingroup$ If you have $P,S_1$ with $P=2kS_1$, then you can compute $k$ by computing the heights of $P$ and $S_1$. $\endgroup$– Felipe VolochOct 8, 2013 at 14:18

$\begingroup$ Yes, but I need another method! Without using height function!As I know, we can't compute the exact value of $\hat{h}(P)$, on the other hand, I don't know the complexity of computing the height functions. $\endgroup$– somayeh didariOct 8, 2013 at 15:05

$\begingroup$ Sage and Magma can compute canonical heights pretty well. $\endgroup$– Daniel LoughranOct 8, 2013 at 20:19

$\begingroup$ I use Pari/gp, and I know it computes canonical height. On the othere hand since $4k^2=\hat{h}(P)/\hat{h}(S_1)$, actually we don't need to know the exact value of the canonical heights! I'm looking for another algorithm. Without using height functions! $\endgroup$– somayeh didariOct 9, 2013 at 5:26
1 Answer
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.