The other day I finished watching the HBO series Silicon Valley, which I recommend by the way (my favourite character is Gilfoyle), at one point they raised this possibility as something catastrophic, so I started researching the subject. The discrete logarithm is a fundamental problem in number theory and cryptography.
The discrete logarithm problem is considered difficult, and this difficulty is the basis of many cryptographic systems, such as the Diffie-Hellman key exchange protocol and the DSA digital signature scheme.
When we say that a solution to a problem is "in polynomial time," we mean that the time it takes to solve the problem grows polynomially with respect to the size of the input, rather than growing exponentially or even faster. Problems that can be solved in polynomial time are considered "efficiently solvable."
So if an AI develops a general solution to the discrete logarithm in polynomial time, it means it has found a way to solve this fundamental problem much more efficiently than previously thought possible. This would have huge implications:
Security Implications: Many cryptographic systems that rely on discrete logarithm difficulty would become insecure. This could compromise the security of communications, financial transactions, and many other systems that rely on discrete logarithm-based cryptography.
Theoretical advance: In terms of the theory of computing and cryptography, such a discovery would be a significant advance, changing the perception of which problems are difficult and which are not.
Research boost: A discovery of this type would prompt a review and redesign of cryptographic systems, in addition to motivating research in related areas to identify other possible advances.
It is important to note that, as far as I know, no such polynomial solution has been found for the discrete logarithm, and it is considered one of the open problems in cryptography and number theory.
What do you think, does this worry you?
To what extent is it a distant or impossible topic?
It would be cool if someone with more knowledge than me (that is, anyone) shed light on the matter.
Top comments (0)