0
$\begingroup$

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

$\endgroup$
5
  • 6
    $\begingroup$ How are you supposed to identify $R$? $\endgroup$ Oct 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$ Oct 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$ Oct 8, 2013 at 15:05
  • $\begingroup$ Sage and Magma can compute canonical heights pretty well. $\endgroup$ Oct 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$ Oct 9, 2013 at 5:26

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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