Introduction
Brute-forcing a discrete logarithm g^x = h mod p takes O(n) trials. The baby-step giant-step algorithm, published by Daniel Shanks in 1971, cuts that to O(sqrt(n)) by splitting the search into two halves and meeting in the middle. This tool runs the algorithm in your browser and shows both halves side by side: the baby-step table of g^0, g^1, ..., g^(m-1) and the giant-step walk through h, h * g^(-m), h * g^(-2m), and so on. When a giant-step value matches a baby-step entry, the discrete log falls out as x = im + j. Paste your generator, target, and modulus, and watch the meet-in-the-middle unfold.
What this tool does
- Solve the discrete logarithm g^x = h (mod p) using Shanks' baby-step giant-step algorithm in O(sqrt(n)) time and space, far faster than the O(n) brute-force approach
- Display the full baby-step table: g^0, g^1, g^2, ..., g^(m-1) mod p, stored in a hash table for O(1) lookup
- Display the giant-step sequence: h * g^(-im) mod p for i = 0, 1, 2, ..., highlighting the value that matches a baby-step entry
- Report the solution x = im + j when a match is found, along with the total number of steps taken
- Accept a configurable order bound m (from 100 to 1,000,000) so you can control the table size and search depth
- Run entirely client-side with BigInt arithmetic, so no inputs leave your browser
How this tool works
The tool takes three inputs: a generator g, a target h, and a prime modulus p. It also accepts an order bound m, which defaults to 100,000. The algorithm sets m = ceil(sqrt(n)) where n is the group order, but the tool lets you cap m to keep the baby-step table within memory limits.
First, the tool builds the baby-step table. It computes g^0 = 1, g^1, g^2, ..., g^(m-1) mod p by iterative multiplication (each entry is the previous one times g, reduced mod p). Each value is stored in a hash table keyed by the residue, with the exponent j as the value. This takes O(m) time and O(m) space.
Next, the tool computes the giant-step factor g^(-m) mod p. It finds the modular inverse of g^m using the extended Euclidean algorithm, then walks through the giant-step sequence: gamma_0 = h, gamma_1 = h * g^(-m), gamma_2 = h * g^(-2m), and so on, each computed by multiplying the previous gamma by g^(-m) mod p. At each step it checks whether gamma_i is in the baby-step hash table. If gamma_i = g^j for some j, then h = g^(im + j), so x = im + j.
The tool displays both tables side by side. For example, with g = 3, h = 13, p = 17: m = ceil(sqrt(16)) = 4. Baby steps: 3^0 = 1, 3^1 = 3, 3^2 = 9, 3^3 = 10. Giant steps: h * g^(-0) = 13, h * g^(-4) = 13 * 3^(-4) mod 17. Since 3^4 = 13 mod 17, we have 3^(-4) = 13^(-1) mod 17 = 4, so gamma_1 = 13 * 4 mod 17 = 1. The value 1 is in the baby-step table at j = 0, so x = 1*4 + 0 = 4. Indeed, 3^4 = 81 = 13 mod 17.
How baby-step giant-step works (Shanks 1971)
The baby-step giant-step algorithm was published by Daniel Shanks in 1971 (Shanks 1971), who called it the "baby-step giant-step" method. The idea is a meet-in-the-middle attack on the discrete logarithm. Any exponent x in [0, n-1] can be written as x = im + j where m = ceil(sqrt(n)), 0 <= i < m, and 0 <= j < m. Then g^x = h becomes g^(im+j) = h, which rearranges to g^j = h * g^(-im).
The left side, g^j, depends only on j. The right side, h * g^(-im), depends only on i. So we precompute all m values of g^j (baby steps) and store them in a hash table, then compute the m values of h * g^(-im) (giant steps) one at a time, checking each against the table. A collision gives us both i and j, and x = im + j.
The algorithm is described in detail in Menezes, van Oorschot, and Vanstone's *Handbook of Applied Cryptography* as Algorithm 3.56 (HAC Section 3.6). It runs in O(sqrt(n)) time and uses O(sqrt(n)) space. The space requirement is the main drawback: for a group of order 10^12, the baby-step table holds 10^6 entries, which is manageable, but for a 256-bit subgroup (order ~2^256), the table would need 2^128 entries, which is physically impossible.
This is why Diffie-Hellman with safe primes remains secure against generic attacks. The best known generic algorithm for the discrete logarithm problem in a group of order n runs in Omega(sqrt(n)) steps (Shoup 1997), so BSGS is asymptotically optimal among generic algorithms. Pollard's rho algorithm achieves the same O(sqrt(n)) time bound but uses only O(1) space, making it more practical for large groups. For prime fields specifically, the number field sieve runs in sub-exponential time, which is faster than any generic method for sufficiently large p.
How to use this tool
- Enter the generator g, an integer whose powers generate a subgroup of Z/pZ
- Enter the target h, the value whose discrete logarithm you want to find
- Enter the modulus p (should be prime for a well-defined multiplicative group)
- Optionally adjust the order bound m. The default of 100,000 works for groups up to about 10^10. Increase it for larger groups, up to 1,000,000
- Click Run BSGS. The tool builds the baby-step table, then walks the giant-step sequence
- Read the result badge: if a match is found, x is displayed along with the equation g^x mod p = h. If no match is found within the bound, the tool reports that
- Expand the baby-step and giant-step tables to see the two halves of the meet-in-the-middle search and identify which giant-step value matched which baby-step entry
Real-world examples
Solving a small discrete log with BSGS
Input: g = 3, h = 13, p = 17. The group order is 16, so m = ceil(sqrt(16)) = 4. Baby steps: 3^0 = 1, 3^1 = 3, 3^2 = 9, 3^3 = 10 mod 17. Giant steps: gamma_0 = 13, gamma_1 = 13 * 3^(-4) mod 17 = 13 * 4 mod 17 = 1. The value 1 matches baby step j = 0, so x = 1*4 + 0 = 4. Verification: 3^4 = 81 = 13 mod 17. The algorithm found the answer in 8 steps total (4 baby + 2 giant), versus up to 16 for brute force.
A larger group where brute force is slow
Input: g = 5, h = 3, p = 1009 (a prime). The group order is 1008, so m = ceil(sqrt(1008)) = 32. BSGS builds a table of 32 baby steps and walks at most 32 giant steps, for a total of at most 64 operations. Brute force would need up to 1008. The solution is x = 151, since 5^151 mod 1009 = 3. BSGS finds this in about 48 steps, while brute force would need 152 trials.
When no solution exists
Input: g = 4, h = 3, p = 7. The subgroup generated by 4 mod 7 is {1, 2, 4} with order 3. Since 3 is not in this subgroup, no x satisfies 4^x = 3 mod 7. BSGS builds baby steps 4^0 = 1, 4^1 = 4, 4^2 = 2, then walks giant steps. None of the giant-step values appear in the baby-step table, so the tool reports no solution within the bound. This matches the brute-force result: the subgroup is too small to contain h.
Why a 256-bit subgroup defeats BSGS
Input: g = 2, h = some value, p = a 2048-bit safe prime with a 256-bit subgroup. The subgroup order n is about 2^256, so m = ceil(sqrt(n)) is about 2^128. The baby-step table would need 2^128 entries, each a 256-bit number, requiring about 10^39 bytes of storage. No computer on Earth can hold that. This is the security margin that makes Diffie-Hellman with safe primes resistant to generic attacks.
Comparison with similar methods
| Method | Complexity | Typical use |
|---|---|---|
| Brute force | O(n) time, O(1) space | Small groups only, see Discrete Logarithm Calculator |
| Baby-step giant-step (Shanks 1971) | O(sqrt(n)) time and space | Medium groups, this tool |
| Pollard's rho | O(sqrt(n)) time, O(1) space | Medium to large groups, preferred in practice |
| Pohlig-Hellman | O(sqrt(p_max)) for smooth order | Groups with smooth order (insecure) |
| Number field sieve | L_p[1/3, c] sub-exponential | Prime fields, best known for Z/pZ |
| Shoup's lower bound (1997) | Omega(sqrt(n)) generic | Proves BSGS is asymptotically optimal among generic algorithms |
Limitations or considerations
The baby-step giant-step algorithm requires O(sqrt(n)) space for the baby-step table. For a group of order 10^12, that is about 10^6 entries, which fits comfortably in browser memory. For a group of order 10^18, the table needs 10^9 entries, which will exhaust memory in most browsers. The tool caps the order bound m at 1,000,000, so it can handle groups up to about 10^12 before the table becomes too large.
For groups larger than that, Pollard's rho algorithm is the better choice. It achieves the same O(sqrt(n)) time complexity but uses only O(1) space, trading the hash table for a pseudo-random walk through the group. This tool does not implement Pollard's rho.
The tool assumes p is prime. If p is composite, the group structure of Z/pZ depends on the factorization of p, and the algorithm may not find a solution even when one exists in a subgroup. Use the Miller-Rabin Primality Test to verify p before running BSGS.
BSGS is a generic algorithm, meaning it works in any cyclic group. But for prime fields, the number field sieve is sub-exponential and much faster for large p. No implementation of NFS exists in this tool. For educational comparison of the brute-force approach, see the Discrete Logarithm Calculator.
Frequently asked questions
What is the time-space tradeoff in baby-step giant-step?
Brute force takes O(n) time and O(1) space. BSGS takes O(sqrt(n)) time and O(sqrt(n)) space. You store sqrt(n) baby steps in a hash table, then do sqrt(n) giant-step lookups. The trade is memory for speed: a group of order 10^12 needs 10^6 entries (about 32 MB) instead of 10^12 trials. Pollard's rho gets the same O(sqrt(n)) time with O(1) space, which is why it is preferred for larger groups.
How does BSGS compare to Pollard's rho?
Both run in O(sqrt(n)) time. BSGS uses O(sqrt(n)) space for the baby-step table; Pollard's rho uses O(1) space by following a pseudo-random walk until it finds a collision. BSGS is deterministic and easier to understand, which makes it good for teaching. Pollard's rho is probabilistic but more memory-efficient, so it is the practical choice for large groups like those in elliptic curve cryptography.
Why does the tool cap the order bound at 1,000,000?
The baby-step table holds m entries, each a BigInt. At m = 1,000,000, the table uses roughly 30 to 40 MB of browser memory, which is safe for most devices. Larger tables risk crashing the tab. For groups with order above 10^12, you would need Pollard's rho or a native implementation with compact storage, neither of which this browser tool provides.
Is baby-step giant-step used to break real Diffie-Hellman?
No. Real Diffie-Hellman uses 2048-bit or larger primes with 256-bit subgroups. BSGS would need 2^128 baby steps, which requires about 10^39 bytes of storage. That is physically impossible. BSGS is a generic algorithm, and Shoup (1997) proved that no generic algorithm can do better than Omega(sqrt(n)). The only way to attack real DH faster is the number field sieve, which is sub-exponential but still infeasible for well-chosen 2048-bit groups.
Who invented baby-step giant-step?
Daniel Shanks published the algorithm in 1971 in the Mathematics of Computation journal, in a paper titled "Class number, a theory of factorization, and genera." He developed it for computing class numbers of binary quadratic forms, but it applies to any finite cyclic group. The algorithm is cataloged as Algorithm 3.56 in the Handbook of Applied Cryptography by Menezes, van Oorschot, and Vanstone.
Conclusion
The baby-step giant-step algorithm is the canonical meet-in-the-middle attack on the discrete logarithm problem, and it is asymptotically optimal among generic algorithms. This tool makes the two-phase search visible: you can see the baby-step table fill up and the giant-step walk find its match. For the brute-force comparison, see the Discrete Logarithm Calculator. To understand where DLP hardness matters in practice, try the Diffie-Hellman Key Exchange tool. To verify that your modulus p is prime before running BSGS, use the Miller-Rabin Primality Test.