Discrete Logarithm Problem

The discrete logarithm problem is the computational problem of recovering the exponent x given a group element g, a modulus p, and the value g^x mod p. For carefully chosen large primes and generators, no efficient classical algorithm is known. This asymmetry — exponentiation is easy, its inverse is hard — is the mathematical foundation of the Diffie-Hellman Key Exchange, public-key RSA, and elliptic curve cryptography.

The problem's hardness is unproved — it has not been shown that no polynomial-time classical algorithm exists, only that none has been found. Shor's algorithm solves it in polynomial time on a quantum computer, which is why the security of most deployed public-key infrastructure is conditional on no large-scale quantum computer being built. The search for cryptographic hardness assumptions that survive quantum attack is the project of Post-Quantum Cryptography.