Discrete logarithm problem

The discrete logarithm problem is the task of recovering the exponent x given g and y = g^x in a finite cyclic group, such as the integers modulo a large prime or the points on an elliptic curve. Modular exponentiation is fast to compute in one direction but, for well-chosen groups, believed hard to invert on a classical computer, which makes the problem a foundation of public-key cryptography.

#Cryptographic role and quantum status

The assumed hardness of the discrete logarithm underpins Diffie-Hellman key exchange, the DSA and ECDSA signature algorithms, and elliptic-curve cryptography, where the elliptic-curve variant (ECDLP) allows smaller keys than the integer version. NIST specifies discrete-log key establishment in SP 800-56A. The classical hardness does not survive quantum computing: Shor's algorithm solves both the integer and the elliptic-curve discrete logarithm in polynomial time on a large fault-tolerant quantum computer, the same result that breaks Integer factorization. This is why discrete-log systems are being replaced under post-quantum cryptography.