Timeline for Is there an efficient algorithm to solve ECDLP over global field?
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 5, 2014 at 17:50 | vote | accept | somayeh didari | ||
| Jun 14, 2014 at 16:42 | comment | added | somayeh didari | I read the method in the paper: Lifting and elliptic curve discrete logarithms. Using it, I find a similar, (but) deterministic polynomial time algorithm to solve ECDLP on $E(\mathbb{Q})$, in the case where $E(\mathbb{Q})[4]=\{O\}$. | |
| Dec 12, 2013 at 17:11 | comment | added | joro | This is what I meant. The OP can't make hard for bruteforce instances of ECDLP over Q. The height makes it easier of course. | |
| Dec 12, 2013 at 15:54 | comment | added | Joe Silverman | The discrete logarithm problem is to find $m$ so that $Q=mP$. But you're right in the sense that it's not possible to explicitly pose an ECDLP over $\mathbb{Q}$ in which $m\approx10^{10}$ by writing down the coordinates of $P$ and $Q$ as rational numbers. | |
| Dec 12, 2013 at 15:34 | comment | added | joro | Well, If you can't compute $10^{10} P$ you don't have an instance of discrete logarithm at all I believe. | |
| Dec 12, 2013 at 15:28 | comment | added | Joe Silverman | ... Similarly, if you identify $E(\mathbb{C})\cong\mathbb{C}/L$ for a lattice $L$ (computed to 10000 decimal digits), then you can comute the image of $10^{10}P$ in $E(\mathbb{C})\cong\mathbb{C}/L$ to 10000 decimal digits. | |
| Dec 12, 2013 at 15:26 | comment | added | Joe Silverman | No, you absolutely cannot explicitly compute $10^{10}P$, if by compute you mean write down its coordinates as rational numbers, since its coordinates have numerators and denominators with on the order of $10^{100}$ binary digits! OTOH, we can easily write down $\hat h(10^{10}P)$ to (say) 10000 decimal digits. This is no different from the fact that you cannot explicitly write down the integer $3^{100}$, but you can easily compute its logarithm to 10000 decimal places. ... | |
| Dec 12, 2013 at 14:21 | comment | added | joro | I don't claim the height is not fast. Can you explicitly compute $10^{10} P$ for P in my answer? | |
| Dec 12, 2013 at 14:04 | comment | added | Joe Silverman | Hmmmm... I guess that if $k$ has a couple of hundred digits, you'll need to compute the heights to (say) 100,000 decimal places. That should still be feasible, but probably requires several minutes (or even hours?) of computer time. But Tate's series looks like $\sum A_k$ with $|A_k|=O(1/4^k)$, so converges quite rapidly. And there's an even faster converging method that using AGMs. | |
| Dec 12, 2013 at 14:00 | comment | added | Joe Silverman | It is very efficient. One computes the logarithmic canonical height $\hat h(P)$ as a sum of local heights $\lambda_\infty(P)+\sum_p\lambda_p(P)$. There is a fast-converging series for $\lambda_\infty(P)$ due to Tate that let's you compute it to (say) 100 decimal places in a fraction of a second. The $p$-adic contributions are generally even easier to compute (as described in my paper). Note that one isn't computing $kP$; instead one computes $\hat h(Q)/\hat h(P)$, takes the square root, and rounds to the nearest integer. | |
| Dec 12, 2013 at 13:20 | comment | added | joro | How better is this than bruteforce? The naive height grows quite fast, so one can't explicitly compute $k P$ for $k$ large enough. | |
| Dec 12, 2013 at 12:58 | history | answered | Joe Silverman | CC BY-SA 3.0 |