THE GARDEN

Discrete Logarithm Problem (DLP)

Updated 13 Sep 2026

• •

  What it is

  • •

    Given a group, a generator (or any base element) $g$, and a value $h = g^x$ for some unknown integer $x$, the discrete logarithm problem is to recover $x$. In a "generic" group with no exploitable extra structure, this is believed to require roughly $\sqrt{|G|}$ operations (via algorithms like Baby-Step Giant-Step) — computationally infeasible once the group is large enough (hundreds of bits). This assumed hardness is the foundation Diffie-Hellman, ElGamal, and DSA all build on. Critically, "hard" depends entirely on the group chosen: some groups (small ones, or ones with smooth order) make DLP tractable via specialized algorithms, which is why parameter selection matters so much in practice.

• •

  When to apply

  • •

    This is the named problem sitting underneath essentially every Diffie-Hellman-family challenge — recognizing "I need to solve g^x = h for x" as literally the discrete logarithm problem tells you which family of algorithms (generic: BSGS/Pollard's rho; smooth-order: Pohlig-Hellman; special-structure groups: index calculus and beyond) is relevant.

• •

  Symbols and assumptions

  • •

    $g$ is a group element of known order $n$; $h$ belongs to $\langle g\rangle$. The unknown exponent $x$ is defined modulo $n$. In elliptic-curve notation the same problem is $Q=xP$.

• •

  Math — step by step

  • •
    1. Forward evaluation repeats the operation: compute $g^x$ efficiently by repeated squaring. DLP asks to reverse this map and find an exponent.
  • •
    2. A trial search checks $1,g,g^2,\ldots$ until $h$ appears, costing up to $n$ steps. Baby-step giant-step trades memory for about $\sqrt n$ work.
  • •
    3. Hardness depends on the group and its order. Smooth orders admit Pohlig-Hellman; finite-field groups also have specialized algorithms. Hundreds of bits alone do not establish security.
• •

  Worked example

  • •

    Solve $3^x=5\pmod{11}$. The powers are $3^0=1$, $3^1=3$, $3^2=9$, $3^3=27\equiv5$. Thus $x=3$ is a solution.

  • •

    Because 3 has order 5, the answer is $x\equiv3\pmod5$. Check another representative: $3^8\bmod11=5$ too.

• •

  Python

  • •

    Brute force only makes sense for tiny groups:

  • •

    def brute_dlp(g, h, p):
            val = 1
            for x in range(p):
                if val == h:
                    return x
                val = (val * g) % p
    

• •

  SageMath

  • •

    For anything beyond toy size, use a real algorithm rather than brute force:

  • •

    F = GF(p)
    x = discrete_log(F(h), F(g))   # automatically dispatches to BSGS/Pohlig-Hellman/etc. as appropriate
    

• •

  Related

  • •

    Groups (Group Theory Basics)

  • •

    Diffie-Hellman (Textbook Construction)

  • •

    Pohlig-Hellman Algorithm

  • •

    Baby-Step Giant-Step Algorithm

• •

  Cards

  • •

    What does the discrete logarithm problem ask you to find?

    • •

      Given g and h=g^x in a group, recover the exponent x.

  • •

    Why does "hardness" of DLP depend on which group is chosen, not just its size?

    • •

      Some groups have extra exploitable structure (smooth order, special algebraic form) that specialized algorithms can exploit, even when the group is nominally large — size alone doesn't guarantee hardness.

◌ Explore connections in Graph view