Discrete logarithm: find x such that gˣ ≡ h (mod p). Easy to compute gˣ (fast exponentiation) but hard to invert (no efficient classical algorithm). Baby-step giant-step: O(√p) time and space. Security of Diffie-Hellman, ElGamal, DSA depends on DLP hardness.
How to Use
Enter g, h, p:
- g: Base (generator)
- h: Target
- p: Prime modulus
Baby-Step Giant-Step
Set m=⌈√n⌉ where n=ord(g). Baby steps: compute gʲ for j=0..m−1. Giant steps: compute h·(g⁻ᵐ)ⁱ for i=0..m−1. Match gives x=im+j. O(√n) time and space.
Cryptographic Importance
- Diffie-Hellman key exchange
- ElGamal encryption
- Digital Signature Algorithm (DSA)
- Elliptic curve cryptography (ECDLP variant)
Step-by-Step Instructions
- 1Enter base g.
- 2Enter target h.
- 3Enter prime p.
- 4Solve for x.
- 5Verify gˣ ≡ h.