Baby-Step Giant-Step Algorithm

Updated 13 Sep 2026

• •

  What it is

  • •

    A meet-in-the-middle algorithm for solving the discrete logarithm problem $g^x \equiv h \pmod p$ within a group (or subgroup) of known order $n$, in $O(\sqrt n)$ time and space — dramatically faster than brute-forcing all $n$ possibilities, though still infeasible for the full-size groups real cryptography uses. The trick: write the unknown exponent as $x = im + j$ for $m = \lceil\sqrt n\rceil$ and $0 \le i,j < m$. Precompute and store every "baby step" $g^j$ for $j=0,\dots,m-1$ in a lookup table; then take "giant steps" of size $g^{-m}$ starting from $h$, checking at each step whether the current value matches anything in the table — a match at giant-step $i$ and table entry $j$ means $h \cdot g^{-im} = g^j$, i.e. $x = im+j$.

• •

  When to apply

  • •

    You need to solve a discrete log in a group (or a prime-order subgroup, as the inner step of Pohlig-Hellman) small enough that $\sqrt{|G|}$ operations are actually feasible — anywhere from toy sizes up to maybe 40-50 bits by hand, much further with optimized implementations.

• •

  Symbols and assumptions

  • •

    We solve $g^x=h$ in a subgroup of order $n$. Let $m=\lceil\sqrt n\rceil$ and write $x=im+j$ with $0\le j<m$. Negative exponents mean group inverses.

• •

  Math — step by step

  • •
    1. Rearrange $g^{im+j}=h$ to $g^j=h(g^{-m})^i$. The left side takes only $m$ possible baby steps.
  • •
    2. Store a dictionary mapping $g^j$ to $j$. Start the giant-step value at $h$ and multiply it by $g^{-m}$ once per increment of $i$.
  • •
    3. A match gives $x=im+j$. Reduce modulo $n$ and verify $g^x=h$. Membership and inverse assumptions must hold; a modulus itself is not the exponent search bound.
• •

  Worked example

  • •

    Solve $2^x=13\pmod{23}$; 2 has order 11, so choose $m=4$. Baby steps: $j=0,1,2,3$ map to $1,2,4,8$.

  • •

    $2^4=16$ and $16^{-1}\bmod23=13$ because $16\cdot13=208\equiv1$. Thus each giant step multiplies by 13.

  • •

    At $i=0$ the value is 13, not in the table. At $i=1$ it is $13\cdot13\bmod23=8$, matching $j=3$.

  • •

    Therefore $x=1\cdot4+3=7$. Check: $2^7=128\equiv13\pmod{23}$.

• •

  Python

  • •

    def bsgs(g, h, p, n):
            import math
            m = math.isqrt(n) + 1
            table = {}
            e = 1
            for j in range(m):
                table.setdefault(e, j)
                e = (e * g) % p
            factor = pow(pow(g, m, p), -1, p)
            gamma = h
            for i in range(m):
                if gamma in table:
                    return i * m + table[gamma]
                gamma = (gamma * factor) % p
            return None
    

• •

  SageMath

  • •

    discrete_log()` uses BSGS automatically for groups without further exploitable structure — no need to call it directly unless implementing Pohlig-Hellman by hand:

  • •

    x = discrete_log(F(h), F(g), ord=n)
    

• •

  Related

  • •

    Discrete Logarithm Problem (DLP)

  • •

    Pohlig-Hellman Algorithm

• •

  Cards

  • •

    What's the time/space complexity of Baby-Step Giant-Step, and why is that an improvement over brute force?

    • •

      O(√n) instead of O(n) — trading brute-force's linear search for a meet-in-the-middle split into two √n-sized halves.

  • •

    What does a "match" between the baby-step table and a giant-step value tell you?

    • •

      If h·g^(-im) equals table entry g^j, then the discrete log is x = im + j.

◌ Explore connections in Graph view