The discrete logarithm problem asks for the integer n in y = gⁿ mod p when the prime p, generator g of Zₚ*, and group element y are known. Computing y from g and n is straightforward exponentiation; recovering n is considered hard on classical computers. section 8.3.1
The problem supports public-key constructions in several ways:
- Uses a generator whose powers cover every nonzero residue modulo a prime; for p = 13, 2, 6, 7, and 11 are generators of Z₁₃*. section 8.3.1
- Protects Diffie–Hellman private keys because recovering n from a public value gⁿ mod p requires solving the discrete logarithm problem. section 8.3.1
- Forms a classical public-key trapdoor problem alongside integer factorization, while Shor’s algorithm can solve both efficiently on quantum computers. section 8.3 section 8.5
A small exponentiation table
For p = 13 and generator g = 2, the table gives 2³ mod 13 = 8. Forward exponentiation is visible immediately; the reverse task is to determine which exponent produced a supplied group element. In Diffie–Hellman, participants publish gᵃ mod p and gᵇ mod p, then independently compute the shared value gᵃᵇ mod p while an observer sees only the public values. section 8.3.1
