The Discrete Logarithm Problem

A group $(G, \cdot)$ is a set with an associative binary operation, an identity element, and inverses for every element. A group is cyclic if some element $g \in G$, called a generator, produces every element of the group by repeated application of the operation: $G = \{g^0, g^1, g^2, \dots, g^{n-1}\}$, where $n = |G|$ is the group's order. The smallest positive $k$ with $g^k = e$ (the identity) is the order of $g$; if $g$ generates all of $G$, its order equals $n$. The two cyclic groups cryptography cares about most are $\mathbb{Z}_p^*$ — the nonzero residues modulo a prime $p$ under multiplication — and the point group of an elliptic curve over a finite field, under an addition-like operation. In $\mathbb{Z}_p^*$, exponentiation is repeated multiplication mod $p$; on an elliptic curve, the analogous operation is repeated point addition, often written additively as scalar multiplication $xP$. The Discrete Logarithm Problem is stated as: given a cyclic group $G$, a generator $g$, and an element $h \in G$ known to equal $g^x$ for some integer $x$, find $x$. The value $x$ is called the discrete logarithm of $h$ base $g$, written $x = \log_g h$. This mirrors the ordinary logarithm's role as the inverse of exponentiation, except the arithmetic happens inside a finite group rather than over the reals — and that finiteness is precisely what makes inversion hard rather than a one-line calculus fact. The Discrete Logarithm Assumption (DLA) is the conjecture that no probabilistic polynomial-time algorithm solves the DLP with non-negligible probability, for appropriately chosen groups of appropriately large order.

Computing the easy direction: modular exponentiation

The forward direction — computing $g^x \bmod p$ given $g$ and $x$ — must itself be efficient for the scheme to be usable. Naively multiplying $g$ by itself $x$ times takes $O(x)$ multiplications, which is exponential in the bit length of $x$. The standard trick, square-and-multiply (repeated squaring), exploits the binary expansion of the exponent. ``` function ModExp(g, x, p):

# computes g^x mod p result = 1 base = g mod p while x > 0: if x is odd: result = (result base) mod p base = (base base) mod p x = x // 2 # integer division return result ``` Each loop iteration halves $x$, so the loop runs $O(\log x)$ times, and each iteration does at most two modular multiplications on numbers with $O(\log p)$ bits. This is the operation that makes Diffie-Hellman, ElGamal, and DSA computationally cheap for honest parties, while the reverse problem remains (believed) intractable.

The hard direction: generic discrete-log algorithms

An attacker who only knows $g$, $h$, and the group operation (not any special structure) is limited to generic algorithms. The naive approach — try $x = 0, 1, 2, \dots$ until $g^x = h$ — takes $O(n)$ group operations, where $n$ is the order of $g$. Two smarter generic algorithms do much better.

Baby-step giant-step (BSG) trades time for space to reach $O(\sqrt{n})$. Let $m = \lceil \sqrt{n} \rceil$. Write the unknown exponent as $x = im + j$ with $0 \le i, j < m$. Then

Precompute all "baby steps" $g^j$ for $j = 0, \dots, m-1$ and store them in a hash table keyed by value. Then take "giant steps" $h \cdot (g^{-m})^i$ for $i = 0, 1, \dots$ and check for a match in the table. ``` function BabyStepGiantStep(g, h, n): m = ceil(sqrt(n)) table = empty hash map

# baby steps: store g^j -> j for j = 0..m-1 e = 1 for j in 0 .. m-1: table[e] = j e = (e * g) mod p

# giant steps: look for h (g^-1)^(mi) matching a table entry factor = ModExp(ModInverse(g, p), m, p) # g^{-m} mod p gamma = h mod p for i in 0 .. m-1: if gamma in table: j = table[gamma] return (i m + j) mod n gamma = (gamma factor) mod p return "no solution found" # should not happen if h is truly in

Pohlig-Hellman attacks groups whose order $n$ factors into small primes. If $n = \prod p_i^{e_i}$, the discrete log can be solved modulo each $p_i^{e_i}$ separately (using BSG or Pollard's rho within each small subgroup) and then recombined with the Chinese Remainder Theorem. Its running time is roughly

which is efficient whenever every prime factor $p_i$ of $n$ is small — even if $n$ itself is astronomically large. This is precisely why real systems insist that the group order have a large prime factor: it forces every generic attack back up to $\Omega(\sqrt{p})$ for the largest prime $p \mid n$.

Index calculus: breaking $\mathbb{Z}_p^*$ faster than generic bounds

In the specific group $\mathbb{Z}_p^*$, attackers are not limited to generic algorithms, because the integers have extra structure (factorization into small primes). Index calculus exploits this: it finds the discrete logs of many small primes (a "factor base") by collecting relations from random powers of $g$ that happen to factor completely over the factor base, solving a large sparse linear system for their logs, and then expressing $\log_g h$ in terms of those known logs. Its running time is subexponential,

dramatically faster than the $O(\sqrt{p})$ generic bound. This subexponential attack is the reason prime-field Diffie-Hellman and DSA require moduli of roughly 2048–3072 bits for long-term security, whereas elliptic-curve groups — which currently admit no known subexponential algorithm — achieve comparable security with 256–384-bit keys.

Forward direction (modular exponentiation). Square-and-multiply performs one squaring per bit of the exponent and at most one extra multiplication per set bit, so the total is $O(\log x)$ modular multiplications, each on numbers with $O(\log p)$ bits. Using schoolbook multiplication, each modular multiplication costs $O((\log p)^2)$ bit operations, giving a total of $O((\log x)(\log p)^2)$ — polynomial in the input size. This efficiency is not optional: without it, no honest party could compute their own public key or shared secret in practice.

Correctness of square-and-multiply. The invariant maintained by the loop is that at the start of each iteration,

where $x_0$ is the original exponent and $x$, $\text{base}$, $\text{result}$ are the current loop variables. Initially $\text{result} = 1$, $\text{base} = g$, $x = x_0$, so the invariant holds trivially. If $x$ is odd, folding one factor of $\text{base}$ into $\text{result}$ and halving $x$ (after squaring $\text{base}$) preserves the product; if $x$ is even, squaring $\text{base}$ and halving $x$ preserves it directly, since $\text{base}^x = (\text{base}^2)^{x/2}$. When the loop ends, $x = 0$, so $\text{result} \cdot \text{base}^0 = \text{result} = g^{x_0} \bmod p$, as required.

Reverse direction (discrete log). No polynomial-time algorithm is known for a generic cyclic group. The best generic algorithms — those using only group operations and equality tests, not the internal representation of elements — provably require $\Omega(\sqrt{n})$ group operations; this is a theorem (Shoup, 1997) about generic-group algorithms, not merely an empirical observation, and matches the $O(\sqrt{n})$ upper bound of baby-step giant-step and Pollard's rho. Since $n$ has roughly $\log n$ bits, $\sqrt{n} = 2^{(\log n)/2}$ is exponential in the bit length of the group order — this is what "hard" means precisely.

Why group choice matters. The generic $\Omega(\sqrt{n})$ lower bound is only a lower bound against generic attacks. Pohlig-Hellman shows that if $n$ factors into small primes, the effective security collapses to the square root of the largest prime factor, not of $n$ itself — so groups must be chosen with $n$ (or a large subgroup of it) having a large prime factor. In $\mathbb{Z}_p^*$ specifically, index calculus exploits the extra ring structure of the integers (unique factorization) to beat even the generic bound, achieving subexponential $L_p[1/3, c]$ time; no such factor-base structure is known for generic elliptic curve groups, which is the entire reason Elliptic-Curve Cryptography achieves the same security with dramatically smaller keys.

Space. Baby-step giant-step needs $O(\sqrt{n})$ storage for the hash table, which is often the real bottleneck in practice — Pollard's rho variant achieves the same $O(\sqrt{n})$ time with only $O(1)$ space by using a pseudo-random walk and cycle detection, trading a constant-factor slowdown for eliminating the table.

Let's work entirely inside a small, fully checkable group so every step is verifiable by hand: $p = 23$, and take $g = 5$, which is a generator of $\mathbb{Z}_{23}^*$ (order $n = 22$).

Step 1 — verify $g$ is a generator. The powers of $5 \bmod 23$ must hit all 22 nonzero residues before repeating.

All 22 nonzero residues mod 23 appear exactly once, confirming $5$ has order $22$ and generates the full group.

Step 2 — the forward direction. Suppose Alice picks secret exponent $x = 6$ and publishes $h = 5^6 \bmod 23$. Using square-and-multiply: $6 = 110_2$. ``` base = 5, result = 1, x = 6 (110) x even: base = 5^2 = 25 mod 23 = 2, x = 3 x odd: result = 12 = 2, base = 2^2 = 4, x = 1 x odd: result = 24 = 8, base = 4^2=16, x = 0 -> stop result = 8 ``` So $h = 8$, matching the table above ($5^6 \bmod 23 = 8$). This took 3 loop iterations instead of 6 multiplications — a small example of the $O(\log x)$ savings that becomes dramatic for 256-bit exponents.

Step 3 — the attacker's problem. Eve sees $g = 5$, $p = 23$, $h = 8$, and must find $x$ with $5^x \equiv 8 \pmod{23}$, knowing nothing else. Brute force would try $x = 1, 2, 3, \dots$ and stop at $x = 6$ — feasible here because $n = 22$ is tiny, but this is exactly the approach that becomes hopeless once $n$ has hundreds of bits. Baby-step giant-step, for illustration: $m = \lceil \sqrt{22} \rceil = 5$. Baby steps — store $5^j \bmod 23$ for $j = 0, \dots, 4$:

Giant steps — compute $g^{-m} = 5^{-5} \bmod 23$. Since $5^{22} \equiv 1$, $5^{-5} \equiv 5^{17} \equiv 15$ (from the table). Compute $h \cdot (5^{-5})^i \bmod 23$ for $i = 0, 1, 2, \dots$:

Match found at $i = 1$, $j = 1$, giving $x = im + j = 5(1) + 1 = 6$ — recovering Alice's secret exponent, exactly as expected, in $O(\sqrt{22}) \approx 5$ steps of table-building plus a handful of giant steps, rather than checking all 22 candidates. This toy example is fully breakable by hand precisely because $p = 23$ is minuscule; real Diffie-Hellman deployments use primes with 2048+ bits, making even $O(\sqrt{n})$ generic attacks require roughly $2^{1024}$ operations — safely outside any conceivable computational budget.

The DLP is not an abstract curiosity — it is running, right now, inside nearly every encrypted connection on the internet. TLS 1.3 uses (elliptic-curve) Diffie-Hellman for its default key exchange, relying on the DLP over curves like X25519 or the NIST P-256 curve. SSH sessions negotiate ephemeral shared secrets the same way. Signal and WhatsApp use variants of Diffie-Hellman (the X3DH and Double Ratchet protocols) to establish and continuously refresh encryption keys between messaging endpoints. Digital signature schemes — DSA, ECDSA, and EdDSA — invert the same hardness assumption: signing uses a private discrete-log-style secret, and forging a signature would require solving essentially the same DLP. Cryptocurrencies such as Bitcoin and Ethereum secure every transaction with ECDSA signatures over the secp256k1 curve, meaning the entire security of a blockchain ledger reduces, in the end, to the presumed hardness of the elliptic-curve discrete logarithm. Understanding the DLP is therefore the direct on-ramp to both Diffie-Hellman Key Exchange and Elliptic-Curve Cryptography, the two technologies that carry this hardness assumption into deployed systems.

Ask the tutor: How does the Diffie-Hellman key exchange use the Discrete Logarithm Problem to let two parties agree on a shared secret over a public channel?