Engineering / Mathematics — Discrete Logarithms and Factoring
The Baby Step/Giant Step Method
Shanks' baby step giant step algorithm, its square-root running time, and the time-memory trade-off it embodies.
Executive summary
Baby step giant step computes discrete logarithms in time proportional to the square root of the group order, by writing the unknown exponent in a two-digit representation and matching halves.
It is deterministic and achieves the generic lower bound, at the cost of memory proportional to the square root.
Learning objectives
- Derive the two-digit decomposition.
- State the algorithm and its cost.
- Analyse the time-memory trade-off.
01The decomposition
Write the unknown exponent x in base m = ⌈√q⌉ as x = im + j with 0 ≤ i, j < m. Then the defining equation rearranges into a matching condition.
γ^{im + j} = α ⇒ α · γ^{−j} = (γ^m)^iThe left side depends only on j and the right only on i. Tabulating one side and scanning the other finds the match, and the birthday-style meet in the middle converts a product of ranges into a sum.
02The algorithm
Baby step giant step
generator γ, target α, order qx with γ^x = α- Set m = ⌈√q⌉.
- Baby steps: for j from 0 to m−1, store the pair (α · γ^{−j}, j) in a lookup table.
- Compute δ = γ^m.
- Giant steps: for i from 0 to m−1:
- If δ^i appears in the table with value j, return x = im + j.
- Report no solution.
O(√q) group operations and O(√q) memoryA hash table gives constant expected lookup, so the total is dominated by the 2√q group operations. The method is deterministic — it always finds the answer if one exists, with no probabilistic element.
03The trade-off
| Method | Time | Memory | Deterministic? |
|---|---|---|---|
| Brute force | O(q) | O(1) | Yes |
| Baby step giant step | O(√q) | O(√q) | Yes |
| Pollard's rho | O(√q) | O(1) | No |
| Parallel rho with distinguished points | O(√q / P) | Modest | No |
Pollard's rho achieves the same time with constant memory by detecting a cycle in a pseudorandom walk rather than storing a table. It is randomised rather than deterministic, which is a small price for eliminating the storage requirement.
04Frequently asked questions
Can the table be made smaller by unbalancing the split?
Yes. Choosing m smaller reduces memory and increases time proportionally, so any point on the time-memory curve is reachable. The balanced choice minimises the total operation count.
Does the method need the group order?
It needs an upper bound on the order to size the table. An exact order gives the tightest choice; a bound merely costs a constant factor.
Why is this the generic optimum?
Because a matching lower bound is known: any algorithm treating the group as a black box needs on the order of √q operations. Beating it requires exploiting structure the black-box model forbids.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 271-272.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.