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
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 25, 2019 at 0:13 | comment | added | Mark Schultz-Wu | DL has also been shown to be in quasi-polynomial time for multiplicative groups of finite fields of (fixed) characteristic. If DL were NP-hard I imagine this would violate assumptions like ETH and SETH, but am not an expert. | |
| Nov 22, 2019 at 19:51 | comment | added | JoshuaZ | " I think the feeling is that the discrete logarithm problem is NP hard" This is very likely not the case. Discrete log is in BQP and we're pretty sure that no NP-hard problem is in that class. Discrete log is also in NP intersect co-NP and we're reasonably confident no NP-hard problem is in that intersection also. If it were, the polynomial hierarchy would collapse which would be almost as surprising as P = NP. | |
| Nov 22, 2019 at 16:39 | comment | added | David E Speyer | And long before the fast primality test, there was a fast probabilistic primality test en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test . No one was basing security on the difficulty of prime testing, since probabilistic methods appear to be as good as deterministic ones in practice. | |
| Nov 22, 2019 at 16:25 | comment | added | Jesse Silliman | Didn't they make a fast primality test, not a fast factorization algorithm? | |
| Nov 22, 2019 at 16:17 | history | answered | meh | CC BY-SA 4.0 |