Discrete logarithm

The discrete logarithm problem is the mathematical foundation of much of modern cryptography. In a cyclic group G with generator g, the problem asks: given g and g^k, find the exponent k. In multiplicative notation: given a = g^k mod p, find k. The problem is easy to state and believed to be hard to solve — no classical algorithm solves it in sub-exponential time for well-chosen parameters.

The assumed hardness of the discrete logarithm underpins Diffie-Hellman key exchange, DSA signatures, and elliptic-curve cryptography. The Computational Diffie-Hellman assumption is slightly weaker: given g^a and g^b, computing g^{ab} should be hard. The Decisional Diffie-Hellman assumption is stronger: g^{ab} should be indistinguishable from random.

The best known classical algorithms — index calculus for multiplicative groups, Pollard's rho for elliptic curves — run in time that grows faster than polynomial but slower than exponential. For a 2048-bit prime field or a 256-bit elliptic curve, these algorithms are infeasible with current computing power. But the problem is not provably hard; it is merely believed hard, and unexpected mathematical advances could collapse the assumption overnight.

The quantum threat is concrete. Shor's Algorithm solves the discrete logarithm problem in polynomial time on a sufficiently large quantum computer. This means that a future quantum computer could break Diffie-Hellman, DSA, and ECC simultaneously. The cryptographic community is racing to deploy Post-Quantum Cryptography before that threat materializes.

The discrete logarithm problem is thus a temporary foundation — one of the most consequential mathematical assumptions in the history of security, but one whose days are numbered. The question is not whether it will fall, but when, and whether the transition to quantum-resistant foundations will be complete before the threat becomes real.