Take the 2-minute tour ×

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

share|improve this question
How are you supposed to identify $R$? –  Felipe Voloch Oct 8 '13 at 13:13
If you have $P,S_1$ with $P=2kS_1$, then you can compute $k$ by computing the heights of $P$ and $S_1$. –  Felipe Voloch Oct 8 '13 at 14:18
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. –  somayeh didari Oct 8 '13 at 15:05
Sage and Magma can compute canonical heights pretty well. –  Daniel Loughran Oct 8 '13 at 20:19
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! –  somayeh didari Oct 9 '13 at 5:26

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer

Your Answer


