Hello everyone!!

Toni Cannoli — Fri, 20 Oct 2023 12:01:22 +0000

Hello everyone!
This is Toni from Andalusia, Spain.
First and foremost, I must share that I have a deep appreciation for craft beer, absurd humor, and the beginnings of apocalyptic films. I studied philosophy a few years ago, but I've always been immersed in the tech world as well. Even during my philosophy studies, I had programmer friends who passed on their passion to me, and I've always been intrigued by this field. Currently, I'm in my second year of backend training and am eager to learn as much as I can from the community. Perhaps, if my expertise permits, or if there's a topic where I can be of assistance, I hope to contribute and be of help too. It's a pleasure to be here.

Ever wondered if AI will someday provide a polynomial-time solution for a discrete logarithm? Let's talk about it!

Toni Cannoli — Thu, 19 Oct 2023 16:43:37 +0000

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.

DEV Community: Toni Cannoli

Hello everyone!!

Ever wondered if AI will someday provide a polynomial-time solution for a discrete logarithm? Let's talk about it!