The Discrete Logarithm Problem

Number Theory · Axiom Academy

LESSON The Discrete Logarithm Problem Understanding one of cryptography's most important computational challenges The discrete logarithm problem asks: given a prime p , a generator g , and a value h , find the exponent x such that: The difficulty lies in the structure of modular arithmetic. When we compute powers modulo a prime, the results appear to "wrap around" in an unpredictable way, destroying the obvious patterns we could exploit. Key Insight: The modulo operation "scrambles" the exponential growth, making it a one-way function in practice for large primes. 3. Comparison with Integer Factoring The discrete logarithm problem is often compared to integer factoring—both are believed to be hard, and both underpin modern cryptography. Given N = pq , find primes p and q Given g x ≡ h (mod p) , find x Used in: Diffie-Hellman, ElGamal Similarity: Both problems are easy in one direction (multiplication, exponentiation) but hard in reverse (factoring, discrete log). 4. Baby-Step Giant-Step Algorithm While no efficient general solution exists, the baby-step giant-step algorithm provides a better-than-brute-force approach with time complexity O(√p).

This is the written version of the interactive lesson above. See the full Number Theory course.