Difficulty: Intermediate to Advanced | Prerequisites: Modular arithmetic, modular exponentiation (Section 11 part 1), basic group theory (Z*p), hash tables.
The discrete logarithm problem sits at the heart of Diffie-Hellman key exchange: given g, h, and a prime p, find x such that g^x ≡ h mod p. There is no known polynomial-time algorithm for this, and that hardness is what makes the cryptosystem secure. The Baby-step Giant-step (BSGS) algorithm is the best-known "naive" approach, running in O(√p) time and space. It is not efficient in the complexity-theory sense (the input size is log p, so O(√p) is exponential in the input length), but it is a clean illustration of a time-space tradeoff and a meet-in-the-middle strategy. This section also ties discrete log and integer factorisation to NP-completeness.
Baby-step Giant-step finds the discrete logarithm by splitting the exponent into two halves, precomputing a table of "baby steps" (powers of g), then searching it with "giant steps" (multiples of g^(-m)). The collision gives you x. It runs in O(√p) time, which is better than brute force but still exponential in the input size.
Zₙ (integers mod n)
The set {0, 1, 2, ..., n - 1} with arithmetic performed modulo n. Think of it as a number line that wraps around at n.
Z*p (multiplicative group mod p)
The subset of Zp whose elements have a multiplicative inverse mod p. When p is prime, Z*p = {1, 2, ..., p - 1}, because every non-zero element is coprime to p. In simple terms, these are the numbers you can "divide by" in modular arithmetic when the modulus is prime.
Generator
An element g of Zp such that every element of Zp can be written as some power of g. Formally, {g^x : x ∈ {0, 1, ..., p - 2}} = Z*p. Think of g as a number that, when raised to successive powers mod p, cycles through every non-zero residue before repeating.
Discrete logarithm
Given a generator g, a prime p, and a value h in Z*p, the discrete logarithm is the exponent x such that g^x ≡ h mod p. This is the "reverse" of modular exponentiation: exponentiation is easy, but finding the exponent from the result is believed to be hard.
Baby-step Giant-step (BSGS)
A meet-in-the-middle algorithm that finds the discrete logarithm in O(√p) time and O(√p) space by splitting the unknown exponent into two parts and searching for a collision between two precomputed arrays.
Given a prime p, a generator g of Z*p, and a target h, find x such that g^x ≡ h mod p.
Brute force tries x = 0, 1, 2, ..., p - 2 one at a time, costing O(p) in the worst case. BSGS does better.
Let m = ⌈√p⌉. Write the unknown exponent as x = mq + r, where 0 ≤ r < m and 0 ≤ q ≤ m.
Substituting into h = g^x:
h ≡ g^(mq + r) ≡ g^(mq) · g^r mod p
Rearranging: h · g^(-mq) ≡ g^r mod p
Build two arrays:
Baby steps (array u): compute g^r mod p for r = 0, 1, ..., m - 1. These are successive powers of g.
Giant steps (array v): compute h · (g^(-m))^q mod p for q = 0, 1, ..., m. Each entry jumps by m in the exponent.
Find a collision between u and v. If u[r] = v[q], then g^r ≡ h · g^(-mq) mod p, which gives x = mq + r.
Building each array takes O(√p) time (one multiplication per entry).
Finding the collision:
Naive comparison: O(p), which is no better than brute force.
Sort one array, binary-search the other: O(√p log(√p)).
Use a hash table for one array, look up each element of the other: O(√p).
Overall with hash tables: O(√p) time and O(√p) space.
No, in the complexity-theory sense. The input (the numbers p, g, h) is written in O(log p) bits, so O(√p) = O(2^(log p / 2)), which is exponential in the input length. This is a good thing for cryptography: if the discrete logarithm had a polynomial-time algorithm, Diffie-Hellman would be insecure.
m = \lceil \sqrt{p} \rceilx = mq + r, \quad 0 \le r < mh \cdot g^{-m \cdot q} \equiv g^r \pmod{p}m = ⌈√31⌉ = ⌈5.57⌉ = 6.
Baby steps (compute g^r mod 31 for r = 0 to 5):
g^0 = 1
g^1 = 3
g^2 = 9
g^3 = 27
g^4 = 81 mod 31 = 19
g^5 = 19 × 3 = 57 mod 31 = 26
Compute g^(-m) mod 31:
First find 3^(-1) mod 31. By the extended Euclidean algorithm, 3^(-1) ≡ 21 mod 31. Then g^(-6) = (3^(-1))^6 = 21^6 mod 31 ≡ 2 mod 31.
Giant steps (compute h · (g^(-m))^q = 6 · 2^q mod 31 for q = 0 to m):
q = 0: 6 × 1 = 6
q = 1: 6 × 2 = 12
q = 2: 6 × 4 = 24
q = 3: 6 × 8 = 48 mod 31 = 17
q = 4: 6 × 16 = 96 mod 31 = 3
Find the collision: Baby step r = 1 gives 3, and giant step q = 4 gives 3. So r = 1, q = 4.
x = mq + r = 6 × 4 + 1 = 25.
Verification: 3^25 mod 31 = 6. The discrete logarithm of 6 with respect to generator 3 (mod 31) is 25.
Students sometimes think BSGS is an efficient (polynomial-time) algorithm. It is not. O(√p) is exponential in the input length O(log p). The distinction between the magnitude of p and the bit-length of p is critical here.
A common mistake in the worked example is computing g^(-m) incorrectly. You need the modular inverse of g first (via the extended Euclidean algorithm), then raise that inverse to the mth power.
Some students assume the baby-step array and the giant-step array must be the same length. They do not need to be exactly the same length, but both are O(√p) in size.
Students occasionally confuse the discrete logarithm problem with ordinary logarithms. In ordinary arithmetic, log is easy to compute. In modular arithmetic, no fast general method is known.
⚠️ Be ready to execute the BSGS algorithm by hand for small primes. Know how to compute g^(-m) mod p using the extended Euclidean algorithm.
⚠️ Understand the runtime argument at two levels: O(√p) in terms of the prime itself, but exponential in terms of the input size O(log p). Exams often test whether you can distinguish these.
⚠️ The connection between discrete log, integer factorisation, and NP-completeness is a favourite exam topic. Key facts:
Cracking RSA requires efficient integer factorisation.
Cracking Diffie-Hellman requires efficient discrete logarithm computation.
Both problems are in NP. Neither is known to be in P. Neither is known to be NP-Hard.
If P = NP, both problems would be solvable in polynomial time, breaking modern cryptography.
⚠️ Be able to explain why the lack of a polynomial-time discrete-log algorithm is good news for cryptography, and why BSGS, despite being the fastest known general-purpose method, does not threaten real-world key sizes.
True or false: The BSGS algorithm runs in polynomial time. False. It runs in O(√p), which is exponential in the input length log p.
What is m in the BSGS algorithm when p = 101? m = ⌈√101⌉ = 11.
Fill in the blank: The baby-step array stores successive ______ of the generator g. Powers (g^0, g^1, ..., g^(m-1)).
True or false: If P = NP, then both RSA and Diffie-Hellman are broken. True. Both rely on problems in NP that would then be solvable in polynomial time.
What is the space complexity of BSGS? O(√p), for storing the two arrays.
Q: Walk through the BSGS algorithm to find x such that 2^x ≡ 5 mod 11.
A: p = 11, g = 2, h = 5. m = ⌈√11⌉ = 4. Baby steps: 2^0 = 1, 2^1 = 2, 2^2 = 4, 2^3 = 8. Compute 2^(-4) mod 11: 2^(-1) mod 11 = 6 (since 2 × 6 = 12 ≡ 1), so 2^(-4) = 6^4 = 1296 mod 11 = 9. Giant steps: 5 × 9^0 = 5, 5 × 9^1 = 45 mod 11 = 1. Collision: baby step r = 0 gives 1 and giant step q = 1 gives 1. So x = 4 × 1 + 0 = 4. Check: 2^4 = 16 mod 11 = 5.
Q: Why does the BSGS algorithm guarantee a collision will be found?
A: Because g is a generator of Z*p, some x in {0, ..., p - 2} satisfies g^x = h. Any such x can be written as x = mq + r with 0 ≤ r < m and 0 ≤ q ≤ m (since m = ⌈√p⌉ covers the range). That pair (r, q) produces matching entries in the baby-step and giant-step arrays.
Q: Explain why both integer factorisation and discrete logarithm being in NP matters for the P vs NP question.
A: If P = NP, every problem in NP has a polynomial-time algorithm. Since both problems are in NP, a proof that P = NP would immediately yield efficient algorithms for both, breaking RSA (which needs hard factorisation) and Diffie-Hellman (which needs hard discrete log). Conversely, neither problem is known to be NP-Hard, so proving one hard would not imply that all of NP is hard.
Q: What is the advantage of using a hash table over sorting when finding the collision in BSGS?
A: Sorting one array and binary-searching gives O(√p log(√p)). A hash table gives expected O(√p) for both insertion and lookup, removing the log factor.
This connects directly to fast modular exponentiation (Section 11, part 1), which is the "easy direction" that BSGS tries to invert. Computing g^x mod p is O(log x); finding x from g^x mod p is the hard problem BSGS addresses.
The NP-completeness discussion ties this material to the broader complexity theory covered throughout EECS 376: the P vs NP question, NP-Hardness, and reductions. The open status of integer factorisation and discrete log (in NP, not known to be in P or NP-Hard) is a standard exam talking point.
Diffie-Hellman key exchange, covered elsewhere in the course, relies on exactly this hardness assumption: two parties compute shared secrets using modular exponentiation, and an eavesdropper would need to solve the discrete log to recover the key.
Baby-step giant-step, BSGS, discrete logarithm, discrete log, Shanks algorithm, meet-in-the-middle, generator, cyclic group, Z*p, multiplicative group, Diffie-Hellman, RSA, integer factorisation, NP-completeness, P vs NP, modular inverse, extended Euclidean algorithm, EECS 376, hash table collision, time-space tradeoff, O(sqrt p) algorithm.