THE GARDEN

Pohlig-Hellman Algorithm

Updated 13 Sep 2026

• •

  What it is

  • •

    An algorithm that solves the discrete logarithm problem efficiently whenever the group's order (or the order of the base element being used) is smooth — factors entirely into small primes. Rather than attacking the full-size discrete log directly, Pohlig-Hellman uses Lagrange's theorem to "project" the problem down into each small prime-power subgroup separately, solves each much-smaller discrete log there (typically via Baby-Step Giant-Step), and recombines the results via the Chinese Remainder Theorem into the discrete log modulo the full group order. Since each individual subproblem only costs roughly $O(\sqrt{q})$ for its prime-power factor $q$ — far cheaper than $O(\sqrt n)$ against the whole order $n$ — this makes DLP dramatically easier whenever $n$ is smooth, no matter how large $n$ itself is.

• •

  When to apply

  • •

    You need to solve a discrete log in a group whose order (or the relevant base element's order) you can factor into entirely small primes — this is precisely why safe primes ($p=2q+1$) are used defensively, and precisely why constructing a deliberately smooth-order group is such a powerful offensive move against a target who accepts attacker-chosen parameters.

• •

  Symbols and assumptions

  • •

    $n=\operatorname{ord}(g)=\prod_i\ell_i^{e_i}$ is the factored base order. We solve $g^x=h$, first modulo each prime power, then modulo $n$.

• •

  Math — step by step

  • •
    1. Raise both sides to $n/\ell_i^{e_i}$. The new base $g_i=g^{n/\ell_i^{e_i}}$ has order $\ell_i^{e_i}$, and $h_i=h^{n/\ell_i^{e_i}}=g_i^x$ depends only on $x\bmod\ell_i^{e_i}$.
  • •
    2. Solve each smaller DLP. Basic projection can use BSGS on the whole prime power; full Pohlig-Hellman recovers base-$\ell_i$ digits one at a time, reducing each digit to an order-$\ell_i$ problem.
  • •
    3. For digit $a_k$ after partial exponent $x_k=\sum_{j<k}a_j\ell^j$, raise $h g^{-x_k}$ to $n/\ell^{k+1}$. It equals $(g^{n/\ell})^{a_k}$, so only $\ell$ possible digits remain.
  • •
    4. CRT recombines the prime-power residues. Factor the actual base order, and verify the final exponent. Large prime factors remain the expensive part.
• •

  Worked example

  • •

    Solve $2^x=18\pmod{29}$, with $\operatorname{ord}(2)=28=4\cdot7$. For modulus 4, raise to 7: $g_4=2^7=12$, $h_4=18^7=17\pmod{29}$.

  • •

    The powers of 12 are $1,12,28,17$, so $x\equiv3\pmod4$. For modulus 7, raise to 4: $g_7=16$, $h_7=25$.

  • •

    The powers $16^0,\ldots,16^4$ are $1,16,24,7,25$, so $x\equiv4\pmod7$.

  • •

    Numbers equal to 4 modulo 7 are 4,11,18,25; only 11 is 3 modulo 4. Hence $x=11\bmod28$. Check $2^{11}\bmod29=18$.

• •

  Python

  • •

    def pohlig_hellman(g, h, p, order, factors):
            # factors: dict of {prime: exponent} for `order`'s factorization
            residues, moduli = [], []
            for q, e in factors.items():
                qe = q**e
                gi = pow(g, order // qe, p)
                hi = pow(h, order // qe, p)
                xi = bsgs(gi, hi, p, qe)
                residues.append(xi)
                moduli.append(qe)
            from sympy.ntheory.modular import crt
            x, _ = crt(moduli, residues)
            return int(x)
    

• •

  SageMath

  • •

    discrete_log() runs Pohlig-Hellman automatically whenever it can factor the group's order — this is the practical, standard route rather than hand-rolling the CRT-combination step:

  • •

    F = GF(p)
    x = discrete_log(F(h), F(g))   # dispatches to Pohlig-Hellman when the order is smooth
    

• •

  Related

  • •

    Discrete Logarithm Problem (DLP)

  • •

    Baby-Step Giant-Step Algorithm

  • •

    Chinese Remainder Theorem

  • •

    Smooth Numbers & Constructing Smooth Primes

• •

  Cards

  • •

    What property of a group's order does Pohlig-Hellman specifically exploit?

    • •

      Smoothness — the order factoring entirely into small primes, letting the DLP be solved piecewise in each small prime-power subgroup instead of all at once.

  • •

    What two techniques does Pohlig-Hellman combine internally?

    • •

      Baby-Step Giant-Step (to solve each small prime-power subproblem) and the Chinese Remainder Theorem (to recombine the pieces into the full answer).

◌ Explore connections in Graph view