Discrete Logarithms
The discrete logarithm problem is the foundation of Diffie-Hellman key exchange and many other cryptographic protocols. It's easy to compute powers, but hard to find the exponent.
Given g, h, and p, find x such that g^x ≡ h (mod p)
The One-Way Property: Computing g^x mod p is fast (using square-and-multiply). But finding x given only the result? That's believed to be computationally hard for large primes.
One-Way Function Demo
Forward (Easy)
Compute g^x mod p:
Result appears here...
Reverse (Hard)
Find x given g^x = h mod p:
Result appears here...
Power Table
For small primes, we can see all powers of g mod p:
Discrete Log Puzzle
Can you find the secret exponent x?
Click "New Puzzle" to start...
Enter your guess above...
Why This Is Hard
For small primes, we can find discrete logs by trying all possibilities. But as p grows:
| Prime Size | Possibilities to Check | Time at 1 billion/sec |
|---|---|---|
| 20 bits | ~1 million | 0.001 seconds |
| 40 bits | ~1 trillion | ~17 minutes |
| 80 bits | ~10^24 | ~31 million years |
| 2048 bits (DH) | ~10^616 | Longer than the universe |
Security Foundation: The difficulty of the discrete log problem is why Diffie-Hellman key exchange is secure. An eavesdropper sees g^a and g^b but cannot efficiently compute g^(ab) without knowing a or b.