Timeline for Smart elliptic curve rational point search given Reg*#Sha
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 6, 2012 at 0:21 | comment | added | Noam D. Elkies | Actually I wasn't going to use descent (though naturally descent helps). Suppose I know $\hat h(P)$ to high precision, and also know in which component $P$ goes modulo each factor $p$ of $\Delta_E$ where $c_p > 1$. Then $\exp \hat h(P)$ is a transcendental homogeneous function of the numerator and denominator of $x(P)$. This lets us find the numerator and denominator in time $\exp \epsilon \hat h(P)$. Unfortunately this requires lattice reduction in dimension $\sim \epsilon^{-2}$, so it is not practical to make $\epsilon$ at all small. | |
| Feb 5, 2012 at 13:56 | comment | added | Michael Stoll |
@Joe: I didn't mean to imply that your algorithm was not useful, only that it is not faster when applied to search for a generator. Regarding your suggestion to use both $E$ and $E'$, this will only be faster when the generator of the other curve is the smaller one.
|
|
| Feb 5, 2012 at 13:30 | comment | added | Joe Silverman | @Michael: Good point. But regarding your added comment, couldn't one use the $L$-series value on both $E$ and its 2-isogenous curve $E'$ in parallel, thereby automatically getting the 2-factor gain, since on one of the curves, the height will be smaller. In any case, I wasn't suggesting that the algorithm in my paper was better (or even as good) as other methods, but I think it does give one answer to the OP's question. Also, if you have a curve where the generator is huge, my algorithm can be used to efficiently show that $E(\mathbb{Z})=\emptyset$, which could be useful. | |
| Feb 5, 2012 at 13:07 | history | edited | Michael Stoll | CC BY-SA 3.0 |
deleted 1 characters in body
|
| Feb 5, 2012 at 13:06 | comment | added | Michael Stoll | Reading the original question again, one of the assumptions was that there is a rational 2-torsion point. If you use the covering curve coming from 2-isogeny descent, the height goes down by a factor of 2, and so you get a linear search algorithm, which has the same complexity as Joe Silverman's. So I would say the answer to the original question is No. | |
| Feb 5, 2012 at 10:11 | history | answered | Michael Stoll | CC BY-SA 3.0 |