I think the discrete logarithm problem is one of the two or three pillars that modern public-key cryptography rests on, alongside integer factorization. Whenever I explain Diffie-Hellman key exchange, ElGamal encryption, DSA signatures, or elliptic curve cryptography to someone, I always end up circling back to this one core idea: in certain mathematical groups, computing $g^x \bmod p$ is easy, but going backwards — given $g$, $p$, and $g^x \bmod p$, finding $x$ — is believed to be extremely hard. That asymmetry, that one-way difficulty, is what I want to unpack in this file, covering both how discrete logs are generated/used constructively and the algorithms used to attack (compute) them.
History and Background
I trace the discrete logarithm problem’s cryptographic relevance to Whitfield Diffie and Martin Hellman’s 1976 paper “New Directions in Cryptography,” which introduced the Diffie-Hellman key exchange — the very first published public-key construction, built directly on the presumed hardness of the discrete log problem in the multiplicative group of integers modulo a prime. Taher ElGamal extended this in 1985 into a full public-key encryption and signature scheme. On the attacking side, algorithms for actually computing discrete logarithms have a long history reaching back to Gauss-era number theory, but the modern algorithmic attacks I care about here — Baby-step Giant-step (Shanks, 1971), Pollard’s rho method (1978), the Pohlig-Hellman algorithm (1978), and index calculus methods — were developed through the 1970s and refined ever since, directly shaping how large cryptographic parameters need to be chosen to stay secure.
Problem Statement
Formally, given a finite cyclic group $G$ with generator $g$, and given an element $h \in G$ such that $h = g^x$ for some integer $x$, the discrete logarithm problem asks me to find $x$. In the cryptographically relevant case, $G$ is usually the multiplicative group of integers modulo a large prime $p$ (or a subgroup of it), or the group of points on an elliptic curve. The “generation” side of this topic is about how I construct secure parameters (choosing $g$, $p$, and the group structure) so that the discrete log problem is hard in that group; the “computation” side is about the algorithms an attacker (or a legitimate party solving a known-hard cryptanalysis benchmark) would use to actually try to recover $x$.
Core Concepts
- Cyclic group – a group generated by repeatedly applying the group operation to a single element (the generator); in $\mathbb{Z}_p^*$, this generator is often called a primitive root.
- Order of a group/element – the smallest positive integer $n$ such that $g^n = 1$; this determines the size of the search space for the discrete log problem in that group.
- Primitive root modulo p – a generator $g$ of the full multiplicative group $\mathbb{Z}_p^*$, meaning its powers produce every nonzero residue modulo $p$.
- Subgroup attacks / Pohlig-Hellman – if the group order has small prime factors, the discrete log problem can be solved efficiently in each small subgroup and then combined using the Chinese Remainder Theorem, which is why safe primes (where $(p-1)/2$ is also prime) are preferred in practice.
- Baby-step Giant-step – a meet-in-the-middle algorithm that computes the discrete log in $O(\sqrt{n})$ time and space, where $n$ is the group order.
- Pollard’s rho for discrete logs – a randomized algorithm achieving similar $O(\sqrt{n})$ time complexity but with much lower memory requirements than baby-step giant-step.
- Index calculus – a subexponential algorithm applicable to groups like $\mathbb{Z}_p^*$ (but notably not to generic elliptic curve groups), which is why elliptic curve discrete logs generally require much smaller key sizes for equivalent security compared to the classic multiplicative group setting.
How It Works
I’ll describe both directions: generating secure discrete-log parameters, and computing a discrete log (as an attacker would).
Parameter generation (defender’s side):
- I choose a large prime $p$, ideally a “safe prime” where $q = (p-1)/2$ is also prime, to avoid small subgroup attacks.
- I find a generator $g$ of a large-order subgroup of $\mathbb{Z}_p^*$ (often the subgroup of order $q$), by testing candidate values and confirming their multiplicative order is large.
- I publish $p$ and $g$ as public parameters. A private key $x$ is chosen randomly, and the corresponding public value $h = g^x \bmod p$ is published, while $x$ remains secret.
Baby-step Giant-step (attacker’s side), to compute $x$ given $g, h, p, n$ (group order):
- I compute $m = \lceil \sqrt{n} \rceil$.
- I build a table of “baby steps”: for each $j$ from $0$ to $m-1$, I compute and store $g^j \bmod p$.
- I compute the “giant step” factor $g^{-m} \bmod p$.
- Starting with $\gamma = h$, I repeatedly check whether $\gamma$ matches any entry in my baby-step table; if it does, at iteration $i$ with match at $j$, then $x = i \cdot m + j$.
- If no match, I update $\gamma = \gamma \cdot g^{-m} \bmod p$ and try again, up to $m$ giant steps.
Pollard’s rho (attacker’s side), an alternative that saves memory:
- I define a pseudo-random iteration function that partitions group elements into a small number of sets and updates a running value using $g$ and $h$ exponents depending on which set the current value falls into.
- I run two “walkers” through this sequence at different speeds (tortoise and hare), watching for a collision (the same group element reached via two different exponent combinations).
- Once a collision is found, the difference in the accumulated exponents gives me a linear equation in $x$, which I solve (often via modular inverse, handling the case of a shared factor with the group order carefully).
Working Principle
I think of the discrete logarithm’s hardness as coming from the fact that exponentiation in these groups mixes information in a way that’s easy to compute forward (via fast modular exponentiation, exploiting the structure of repeated squaring) but has no known efficient “undo” operation in a generic group — unlike, say, ordinary real-number logarithms, which have closed-form inverses. Baby-step giant-step exploits a simple algebraic rewriting: any exponent $x$ less than $n$ can be written as $x = im + j$ for $0 \le i, j < m$, turning the search into two smaller searches that meet in the middle, at the cost of needing $O(\sqrt{n})$ storage. Pollard’s rho instead relies on the birthday paradox: a pseudo-random walk over a group of size $n$ is expected to produce a collision after roughly $O(\sqrt{n})$ steps, and because the walk’s structure ties each element to a specific combination of $g$ and $h$ exponents, a collision translates directly into a linear equation revealing $x$ — all without needing to store the whole path, unlike baby-step giant-step.
Mathematical Foundation
The discrete logarithm problem: given $g, h \in G$ with $h = g^x$, find $x$ such that:
$$g^x \equiv h \pmod{p}$$
Baby-step giant-step decomposition, writing $x = i m + j$ with $m = \lceil \sqrt{n} \rceil$:
$$h = g^{im+j} \implies h \cdot g^{-im} = g^{j} \implies h \cdot (g^{-m})^{i} = g^{j}$$
I search for a match between the baby-step table ${g^j : 0 \le j < m}$ and the giant-step sequence ${h \cdot (g^{-m})^i : 0 \le i < m}$.
Pollard’s rho collision equation: if two points in the pseudo-random walk collide, meaning $g^{a_1} h^{b_1} = g^{a_2} h^{b_2}$, then since $h = g^x$:
$$g^{a_1 + b_1 x} = g^{a_2 + b_2 x} \implies a_1 + b_1 x \equiv a_2 + b_2 x \pmod{n} \implies x \equiv \frac{a_1 – a_2}{b_2 – b_1} \pmod{n}$$
Pohlig-Hellman, for a group order $n = \prod p_i^{e_i}$, reduces the problem to computing $x \bmod p_i^{e_i}$ for each small prime power factor independently, then reconstructing $x$ via the Chinese Remainder Theorem:
$$x \equiv x_i \pmod{p_i^{e_i}} \text{ for each } i, \quad \text{combine via CRT to recover } x \bmod n$$
which is precisely why $n$ (the group order, or the order of the subgroup used) must have a large prime factor for the discrete log problem to remain hard.
Diagrams
flowchart TD
A[Choose large prime p and generator g] --> B[Compute group order n = p-1 or subgroup order q]
B --> C[Check n has a large prime factor - avoid Pohlig-Hellman weakness]
C --> D[Publish g, p as system parameters]
D --> E[Private key x chosen randomly]
E --> F[Public key h = g^x mod p]
F --> G[Discrete log problem: recover x from g,h,p - believed hard]
Pseudocode
// Baby-step Giant-step algorithm
function baby_step_giant_step(g, h, p, n):
m = ceil(sqrt(n))
table = empty_hash_map()
for j in 0..m-1:
table[pow_mod(g, j, p)] = j
g_inv_m = pow_mod(mod_inverse(g, p), m, p)
gamma = h
for i in 0..m-1:
if gamma in table:
j = table[gamma]
return i * m + j
gamma = (gamma * g_inv_m) mod p
return "no solution found"
// Pollard's rho for discrete logarithms (simplified)
function pollard_rho_dlog(g, h, p, n):
define step(x, a, b):
subset = x mod 3
if subset == 0: return (x*x mod p, 2*a mod n, 2*b mod n)
if subset == 1: return (x*g mod p, (a+1) mod n, b)
return (x*h mod p, a, (b+1) mod n)
x1, a1, b1 = 1, 0, 0
x2, a2, b2 = 1, 0, 0
repeat:
x1, a1, b1 = step(x1, a1, b1) // tortoise: one step
x2, a2, b2 = step(x2, a2, b2) // hare: two steps
x2, a2, b2 = step(x2, a2, b2)
until x1 == x2
numerator = (a1 - a2) mod n
denominator = (b2 - b1) mod n
return (numerator * mod_inverse(denominator, n)) mod n
Step-by-Step Example
I’ll work a small example with Baby-step Giant-step, small enough to trace by hand.
- Let
p = 23, and I chooseg = 5, which is a primitive root modulo 23 (its powers generate all of1..22). The group order isn = 22. - Suppose the public value is
h = 8, and I want to findxsuch that5^x mod 23 = 8. - I compute
m = ceil(sqrt(22)) = 5. - I build my baby-step table for
j = 0..4:5^0=1, 5^1=5, 5^2=25 mod 23=2, 5^3=10, 5^4=50 mod 23=4. Table:{1:0, 5:1, 2:2, 10:3, 4:4}. - I compute
g^-1 mod 23. Since5*14 = 70 = 3*23+1,g^-1 = 14. Theng^-m = 14^5 mod 23. Computing stepwise:14^2=196 mod23=12,14^4=12^2=144 mod23=6,14^5=6*14=84 mod23=84-69=15. Sog^-m = 15. - I start
gamma = h = 8. Check if8is in my table — it’s not. - Giant step
i=1:gamma = 8*15 mod 23 = 120 mod 23 = 120-115=5. Check table:5is there, withj=1! - So
x = i*m + j = 1*5 + 1 = 6. - I verify:
5^6 mod 23 = 15625 mod 23. Computing:5^2=25mod23=2,5^4=2^2=4,5^6=5^4*5^2=4*2=8. Yes,5^6 mod 23 = 8, confirmingx = 6is correct.
Time Complexity
- Brute force search: $O(n)$, trying every possible exponent.
- Baby-step Giant-step: $O(\sqrt{n})$ time and $O(\sqrt{n})$ space, since I build and query a table of size roughly $\sqrt{n}$.
- Pollard’s rho: $O(\sqrt{n})$ expected time, but only $O(1)$ additional space (beyond the tortoise/hare state), making it far more practical for large groups than Baby-step Giant-step.
- Pohlig-Hellman: efficient (polynomial in the bit-length of $n$ and the size of the largest prime factor) whenever the group order $n$ is “smooth” (composed only of small prime factors); this is precisely why cryptographic implementations insist on group orders with at least one large prime factor.
- Index calculus (for $\mathbb{Z}_p^*$): subexponential time, roughly $L_p[1/3, c]$ for some constant $c$ in the standard L-notation, which is why key sizes for classical (non-elliptic-curve) discrete log systems need to be much larger (e.g., 2048+ bits) than elliptic curve discrete log systems (where index calculus doesn’t apply and $O(\sqrt{n})$-style attacks are the best known).
Space Complexity
Baby-step Giant-step requires $O(\sqrt{n})$ space to store its lookup table, which becomes impractical for very large groups (a 128-bit security level would require storing roughly $2^{64}$ table entries, well beyond feasible memory). Pollard’s rho needs only $O(1)$ space for its core walk, which is why it’s the practical choice for attacking (or benchmarking) larger discrete log instances. Index calculus methods require more substantial space to store relations and perform linear algebra over a “factor base,” typically $O(L_p[1/3, c])$ as well, subexponential but still large for cryptographic-sized primes.
Correctness Analysis
I can verify Baby-step Giant-step’s correctness directly from the algebraic identity $x = im + j \implies h \cdot g^{-im} = g^j$: every valid exponent $x$ in the range $[0, n)$ has a unique representation as $im+j$ with $0 \le i, j < m$, so the algorithm is guaranteed to find a match within $m$ giant steps if a solution exists, and the match directly yields the correct $x$. Pollard’s rho’s correctness relies on the birthday-paradox argument: because the pseudo-random walk function is deterministic given the current state, and the state space is finite, the sequence must eventually cycle (enter a “rho” shape), and detecting the collision via Floyd’s cycle-detection (tortoise and hare) is guaranteed to terminate; the correctness of the recovered $x$ follows from the linear relationship between the accumulated exponents at the collision point, as I derived in the mathematical foundation section — though I do have to be careful about the case where $\gcd(b_2 – b_1, n) \ne 1$, which requires special handling since a modular inverse might not exist directly.
Advantages
- Discrete-log-based systems like Diffie-Hellman allow secure key agreement between parties without any prior shared secret, which was revolutionary when introduced.
- The problem generalizes cleanly to other group structures (like elliptic curves), letting cryptographers achieve the same security level with much smaller key/parameter sizes than classical modular exponentiation groups.
- The attack algorithms (Baby-step Giant-step, Pollard’s rho) are conceptually elegant and give cryptographers precise, well-understood formulas for how large parameters need to be to resist known attacks, which supports rigorous, quantifiable security parameter selection.
Disadvantages
- Discrete log-based systems in $\mathbb{Z}_p^*$ require increasingly large prime moduli (2048 bits or more today) to stay ahead of index calculus attacks, which makes computation slower compared to elliptic curve alternatives at equivalent security levels.
- Poor parameter generation (small subgroups, non-safe primes) can catastrophically weaken security via the Pohlig-Hellman algorithm, so implementers must be careful and precise when generating parameters.
- Like factoring-based systems, discrete-log-based cryptography (in the classical, non-lattice-based sense) is vulnerable to Shor’s algorithm on a sufficiently powerful quantum computer, which is part of why the field is now moving toward post-quantum alternatives.
Applications
Discrete logarithm hardness underlies Diffie-Hellman key exchange (used constantly in TLS/SSL for establishing session keys), the Digital Signature Algorithm (DSA) and ElGamal signatures/encryption, and — in its elliptic curve form — Elliptic Curve Diffie-Hellman (ECDH) and ECDSA, which power much of modern TLS, SSH, cryptocurrency transaction signing, and secure messaging protocols. I also see discrete log algorithms (Baby-step Giant-step, Pollard’s rho) used directly in cryptanalysis research and in solving discrete log “challenge” problems used to benchmark real-world security margins.
Implementation in C
#include <stdio.h>
#include <stdint.h>
#include <math.h>
/* modular exponentiation: base^exp mod mod */
long long pow_mod(long long base, long long exp, long long mod) {
long long result = 1;
base %= mod;
while (exp > 0) {
if (exp & 1) result = (result * base) % mod;
base = (base * base) % mod;
exp >>= 1;
}
return result;
}
/* extended Euclidean algorithm for modular inverse */
long long mod_inverse(long long a, long long m) {
long long m0 = m, t, q;
long long x0 = 0, x1 = 1;
a = ((a % m) + m) % m;
if (m == 1) return 0;
while (a > 1) {
q = a / m;
t = m; m = a % m; a = t;
t = x0; x0 = x1 - q * x0; x1 = t;
}
if (x1 < 0) x1 += m0;
return x1;
}
/* Baby-step Giant-step: find x such that g^x = h (mod p), 0 <= x < n */
long long baby_step_giant_step(long long g, long long h, long long p, long long n) {
long long m = (long long)ceil(sqrt((double)n));
/* simple table: linear search for teaching clarity (a hash map
would be used in a production implementation for speed) */
long long *values = malloc(m * sizeof(long long));
long long cur = 1;
for (long long j = 0; j < m; j++) {
values[j] = cur;
cur = (cur * g) % p;
}
long long g_inv = mod_inverse(g, p);
long long g_inv_m = pow_mod(g_inv, m, p);
long long gamma = h % p;
long long answer = -1;
for (long long i = 0; i < m && answer == -1; i++) {
for (long long j = 0; j < m; j++) {
if (values[j] == gamma) {
answer = i * m + j;
break;
}
}
gamma = (gamma * g_inv_m) % p;
}
free(values);
return answer;
}
int main(void) {
long long p = 23, g = 5, h = 8, n = 22; /* group order p-1 = 22 */
long long x = baby_step_giant_step(g, h, p, n);
printf("p = %lld, g = %lld, h = %lld\n", p, g, h);
printf("Discrete log x such that g^x mod p = h: x = %lld\n", x);
printf("Verification: g^x mod p = %lld\n", pow_mod(g, x, p));
return 0;
}
Sample Input and Output
Input: p = 23, g = 5, h = 8, group order n = 22, solved with the Baby-step Giant-step implementation above.
Output:
p = 23, g = 5, h = 8
Discrete log x such that g^x mod p = h: x = 6
Verification: g^x mod p = 8
This matches my hand-worked example exactly.
Optimization Techniques
- Replacing the linear-search table lookup in my educational C implementation with a real hash table reduces Baby-step Giant-step’s per-query cost from $O(\sqrt{n})$ to $O(1)$ amortized, which is essential for practical-sized problems.
- Using Pollard’s rho with parallelization (running many independent walks across multiple processors, using distinguished points to detect collisions across walkers) dramatically reduces wall-clock time for large-scale discrete log computations — this is exactly the approach used in real discrete-log “record” computations.
- Choosing safe primes (or otherwise ensuring the group order has a large prime factor) during parameter generation preemptively defeats Pohlig-Hellman-style attacks, which is far cheaper than trying to detect a bad prime after the fact.
- Precomputing and caching modular inverses and fixed powers of the generator, when many discrete log queries will be made against the same group, amortizes the setup cost.
Common Mistakes
- Choosing $p$ or the subgroup order without checking for small prime factors, opening the door to efficient Pohlig-Hellman attacks.
- Reusing the same random exponent (nonce) across multiple discrete-log-based signature operations (as in DSA/ECDSA), which — while not a discrete log algorithm mistake per se — is one of the most common real-world implementation failures that leaks the private key through simple linear algebra on signature equations.
- Implementing Baby-step Giant-step with a slow table lookup (like linear search, as I used above purely for teaching clarity) in a performance-critical context, which negates the whole point of the algorithm’s improved time complexity.
- Assuming that because an elliptic curve group has no efficient index calculus attack, any curve is automatically secure — poorly chosen curves can still have exploitable structure (small subgroup issues, invalid curve attacks, or weak curve parameters), so standardized, well-vetted curves should always be used.
- Forgetting that discrete-log-based schemes (in their classical, non-post-quantum form) are considered breakable by a sufficiently powerful quantum computer running Shor’s algorithm, which matters for anyone doing long-term security planning today.
Further Reading
- Diffie, W. and Hellman, M., “New Directions in Cryptography,” IEEE Transactions on Information Theory, 1976: https://ee.stanford.edu/~hellman/publications/24.pdf
- Pohlig, S. and Hellman, M., “An Improved Algorithm for Computing Logarithms over GF(p) and Its Cryptographic Significance,” 1978: https://ee.stanford.edu/~hellman/publications/28.pdf
- Pollard, J., “Monte Carlo Methods for Index Computation (mod p),” Mathematics of Computation, 1978: https://www.ams.org/journals/mcom/1978-32-143/S0025-5718-1978-0491431-9/
- Menezes, van Oorschot, and Vanstone, Handbook of Applied Cryptography, Chapter 3: https://cacr.uwaterloo.ca/hac/about/chap3.pdf
- NIST Special Publication 800-56A on discrete-log-based key establishment schemes: https://csrc.nist.gov/pubs/sp/800/56/a/r3/final
