Discrete logarithm calculator

How it works

Given $g$, $h$ and a modulus $p$, the discrete logarithm is an exponent $x$ with $g^x \equiv h \pmod p$. Computing $g^x$ from $x$ takes a few hundred multiplications by square and multiply; going back is believed to be hard. This one-way property is what Diffie-Hellman, ElGamal and DSA rely on.

Trying $x = 0, 1, 2, \dots$ needs up to $\operatorname{ord}(g)$ steps. Shanks’ baby-step giant-step method trades memory for time: with $m = \lceil \sqrt{\operatorname{ord}(g)} \rceil$, write $x = im + j$, store the baby steps $g^j$ for $j < m$, then compute the giant steps $h \cdot g^{-im}$ until one of them appears in the store. That costs about $2\sqrt{\operatorname{ord}(g)}$ multiplications.

Even so, a group of order $2^{256}$ needs $2^{128}$ steps. Modulo a prime, index calculus methods are faster, which is why such groups need primes of 2048 bits or more; if the order of $g$ has only small prime factors, the Pohlig-Hellman reduction makes the problem easy, so real systems use a subgroup of large prime order.