Discrete Logarithm

The discrete logarithm problem is the computational task of finding an integer k such that g^k ≡ h (mod p), given a prime p, a primitive root g modulo p, and a target h. It is the modular arithmetic analogue of the ordinary logarithm, and like its continuous cousin, it transforms multiplicative structure into additive structure — but unlike the continuous case, no efficient classical algorithm is known for computing it in general.

The hardness of the discrete logarithm problem in certain groups — particularly the multiplicative groups of finite fields and the point groups of elliptic curves — is the foundation of modern public-key cryptography. The Diffie–Hellman key exchange, ElGamal encryption, and the Digital Signature Algorithm all depend on the assumption that discrete logarithms cannot be computed in polynomial time by classical computers. Shor's algorithm on a quantum computer solves the problem in polynomial time, making discrete-logarithm-based cryptosystems vulnerable to quantum attack.

The discrete logarithm is the computational shadow of cyclic symmetry. Where the continuous logarithm is trivial to compute because the real numbers are a Lie group with a simple exponential map, the discrete logarithm is hard because the finite cyclic group has no such smooth structure. This is not an accident: the hardness is the algebraic price of finiteness, and cryptography is the art of charging that price to an adversary.