Will someone find an efficient algorithm for calculating DIscrete Logarithms on a classical computer?
4
213
130
2030
14%
chance

There is currently no efficient algorithm to calculate a discrete logarithm on a classical computer, this is known as the discrete logarithm problem. Much of cryptography is based on this problem, however there has been no proof that no efficient algorithm exists. Only much work has been done, and no easy way has been found. See: https://en.wikipedia.org/wiki/Discrete_logarithm_problem

Similar to, but not equal to:

Get Ṁ200 play money
Sort by:

How efficient is an "efficient algorithm" (for the purposes of this market)?

If you just want something on the edge of being practical, then index calculus does an amazing job for discrete logarithms over finite fields. OTOH if you want a provably polytime algorithm then I think you'd probably want P vs NP to be resolved.

@duck_master This is about provably polynomial time, also for the edge cases, not just a heuristic that works well in most cases. Such that it's no longer practical to use . ElGamal encryption, Diffie–Hellman key exchange in say peoples browsers.

@FedorBeets In that case I am betting NO.

@duck_master ohh yeah, I think the odds are very low. Which is good for my day job in cybersecurity

That sounds absurdly impossible, especially since logarithms are an invalid concept to begin with (i**4 = -1 and 1 at the same time for example).

The question refers to exponentiation under a finite field, not under complex numbers

@TrippLyons Thanks, but I think he was just trolling. He's a banned user.