Timeline for Is there any theory why (for Bitcoin) the discrete logarithm problem is so hard to solve?
Current License: CC BY-SA 4.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 23, 2019 at 3:44 | answer | added | kodlu | timeline score: 6 | |
| Nov 23, 2019 at 0:56 | history | became hot network question | |||
| Nov 22, 2019 at 23:16 | answer | added | Joe Silverman | timeline score: 24 | |
| Nov 22, 2019 at 19:41 | answer | added | Adam P. Goucher | timeline score: 31 | |
| Nov 22, 2019 at 18:04 | comment | added | David E Speyer | Over on cstheory , Peter Shor writes "there are no good justifications for factoring being hard, other than that nobody has been able to crack it so far." cstheory.stackexchange.com/a/5098/6508 I think the same is true of discrete log. | |
| Nov 22, 2019 at 17:42 | comment | added | Robert Israel | Discrete logarithm (as well as integer factorization) have polynomial-time algorithms for quantum computers (of course we don't yet have quantum computers that can run these algorithms). We do not have polynomial-time algorithms for quantum computers to solve problems that are known to be NP-complete. This suggests strongly that discrete logarithm and integer factorization are not NP-complete. So even if we could prove $P \ne NP$, it would not prove that discrete logarithm is hard. | |
| Nov 22, 2019 at 16:53 | comment | added | Simon Henry | Maybe it is worth mentioning that no such "theory" exists in the sense that nobody knows how to prove that the discrete logarithm problem is hard (e.g. If hard means "not solvable in polynomial time" such a proof would imply $P \neq NP$). It is justs something that everybody believes is the case. Of course that does not mean that one cannot find some kind of heuristic explanation of why it is hard. | |
| Nov 22, 2019 at 16:17 | answer | added | meh | timeline score: -14 | |
| Nov 22, 2019 at 13:13 | comment | added | Chris Wuthrich | I should add that if $n=p$ or $n=p+1$ then we happen to know how to do it. | |
| Nov 22, 2019 at 13:12 | comment | added | Chris Wuthrich | Why is it hard to factor numbers? - Because we don't know a fast way of doing so. I think it is the same here. We just don't know how to do it. Look at the points $g^x$, (usally written additively $nP$) and you won't see any pattern that could help you to construct the inverse of $f$. | |
| Nov 22, 2019 at 12:50 | review | First posts | |||
| Nov 22, 2019 at 13:48 | |||||
| Nov 22, 2019 at 12:48 | history | asked | Rene Pickhardt | CC BY-SA 4.0 |