Square-root time by spending square-root memory
Searching a group of order N element by element costs N operations. Baby-step giant-step splits the exponent into two halves, tabulates one and steps through the other, reducing the cost to about √N operations and √N storage. Applied to class groups it converts an analytic approximation to the class number into an exact value, because only a narrow interval needs to be searched.
Learning objectives
- State the baby-step giant-step method and its complexity.
- Apply it to determine the exact order of a group element.
- Use an analytic approximation to bound the search interval.
- Assemble a class group structure from element orders.
- Compare with low-memory alternatives.
Section 01The method
To solve gx = h with 0 ≤ x < N, write x = im + j with m = ⌈√N⌉ and 0 ≤ j < m.
- Set m ← ⌈√N⌉.
- Baby steps: compute gj for j = 0, …, m−1 and store (gj, j) in a hash table. m group operations, m storage.
- Compute u ← g−m once.
- Giant steps: set y ← h. For i = 0, …, m−1:
- If y is in the table with value j, return x = im + j.
- Set y ← y · u.
- Report no solution in range.
For N around 1020 the table holds about 1010 entries — far beyond practical memory. Low-memory alternatives such as Pollard's rho and kangaroo methods achieve the same expected time in constant space, at the cost of being probabilistic.
Section 02Application to class groups
The analytic class number formula gives an estimate h̃ with a provable relative error. Rather than searching all of [1, h̃], it suffices to search the interval the error bound permits — and its width is roughly √h̃, so the search costs about |D|1/4.
- Stage 01Estimate h analyticallyTruncate the Euler product to obtain h̃ with a rigorous relative error bound.
- Stage 02Pick a test idealChoose a prime ideal 𝔽 of small norm as a candidate generator.
- Stage 03Find its orderBaby-step giant-step within the permitted interval finds the exact n with 𝔽n principal.
- Stage 04Assemble the groupThe order divides h. Repeat with further ideals until the orders generate a group of the right size; the structure follows from a Smith normal form.
Without it the search interval would be the full range [1, h], and the method would cost √h ≈ |D|1/4 only if h were known to be near its maximum. The estimate is what narrows the interval and makes the exponent 1/4 rather than 1/2.
Section 03Determining structure
Element orders alone do not determine an abelian group: orders 1, 2, 2, 2, 4, 4, 4, 4 fit both ℤ/2 ⊕ ℤ/4 and ℤ/8 poorly, and larger examples are worse. The structure is settled by discrete logarithms among the generators.
- Compute the order n1 of a first ideal class g1; the cyclic subgroup it generates has that order.
- If n1 = h, the group is cyclic; stop.
- Take a second class g2 and find the least n2 with g2n2 in the subgroup already found, using baby-step giant-step for the discrete logarithm.
- Record the resulting relation as a row of a relation matrix. Each new generator contributes one row.
- Repeat until the generated subgroup has order h; the Smith normal form of the relation matrix gives the structure.
ReferenceFrequently asked questions
Is baby-step giant-step deterministic?
Yes — it examines a systematic set of candidates and is guaranteed to find the answer if it lies in the stated range. That distinguishes it from rho-type methods, which are probabilistic in time though also certain in output.
What if the group order is not known even approximately?
The method can be run with doubling bounds: try N, then 2N, then 4N, and so on. The total cost remains a constant multiple of the final successful run, so the penalty for not knowing the order is modest.
When should Pollard's kangaroo method be used instead?
When memory is the constraint and the answer is known to lie in a limited interval. The kangaroo method achieves comparable expected time in constant space, which is decisive once the baby-step table no longer fits.
NavigateContinue in this stream
Curated next steps from this page. The site also surfaces algorithmically related reading below.
ProvenanceSources and further reading
This page is an original KEVOS explanatory article. It presents the underlying mathematics — definitions, algorithms, complexity results and selection criteria — in KEVOS editorial voice. No text is reproduced from any copyrighted source. Where numerical tables are relevant, KEVOS links to live authoritative databases rather than republishing static values.