Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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
6  
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

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.