Discrete Logarithm Calculator

Find x such that g^x ≡ h (mod p) using the baby-step giant-step algorithm.

Solve: g^x ≡ h (mod p)

Base g

Target h

Modulus p

Baby-step Giant-step

Time complexity: O(sqrt(p))

Space complexity: O(sqrt(p))

1. Baby step: Store g^j for j = 0..m-1

2. Giant step: Check h*(g^-m)^i

3. If match at (i,j): x = im + j

Applications

Diffie-Hellman key exchange
ElGamal encryption
Digital signatures (DSA)
Cryptanalysis

3^x ≡ 13 (mod 17)

x = 4

Order of g

Verified

Yes

Verification

3^4 mod 17 = 13

Correct: equals 13

All Solutions

Solutions are unique modulo the order (16)

x = 4

General: x = 4 + 16k

Hardness

The discrete logarithm problem is believed to be computationally hard for large primes. The security of many cryptographic systems depends on this hardness.

💡

Help us improve!

How would you rate the Discrete Logarithm Calculator?