Pohlig-Hellman

Public-key cryptography rests on a simple-sounding question: given $g^x \bmod p$, find $x$. This is the discrete logarithm problem, and for the right choice of group it is believed to be hard — no algorithm known runs in polynomial time in the general case.

But hard on average does not mean hard always. In 1978, Stephen Pohlig and Martin Hellman published an algorithm that makes discrete log dramatically easier in groups whose order has only small prime factors. The secret ingredient is the Chinese Remainder Theorem (CRT): instead of solving one big problem, you solve many tiny ones — one per prime-power factor of the group order — and stitch the results together.

The algorithm is proven correct and runs in time $O\!\left(\sum_i e_i \left(\log n + \sqrt{p_i}\right)\right)$, where $n = \prod p_i^{e_i}$ is the group order. When every $p_i$ is small (the order is smooth), this is near-linear — exponentially faster than brute force. The lesson cryptographers learned: always work in a group whose order has at least one large prime factor.

Choose a group order and a generator. The demo computes $g^x \bmod p$ for a random secret $x$, then races brute force against Pohlig-Hellman to recover it. Watch what happens when the order is smooth vs. when it has a large prime factor.

<p class="hint">
  {{hint}}
</p>
<div class="controls">
  <label>{{lbl_preset}}
    <select id="preset">
      <option value="smooth16">{{opt_smooth16}}</option>
      <option value="smooth120">{{opt_smooth120}}</option>
      <option value="prime23">{{opt_prime23}}</option>
      <option value="prime53">{{opt_prime53}}</option>
    </select>
  </label>
  <button id="runBtn" type="button">{{btn_run}}</button>
</div>
<div class="info-row" id="groupInfo"></div>
<div class="race">
  <div class="lane" id="laneA">
    <div class="lane-title">{{lane_brute}}</div>
    <div class="lane-body" id="bodyA">—</div>
    <div class="lane-steps" id="stepsA"></div>
  </div>
  <div class="lane" id="laneB">
    <div class="lane-title">{{lane_ph}}</div>
    <div class="lane-body" id="bodyB">—</div>
    <div class="lane-steps" id="stepsB"></div>
  </div>
</div>
<div class="verdict" id="verdict"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: .93rem; }
.hint { color: #444; margin: 0 0 .7rem; line-height: 1.5; }
.controls { display: flex; gap: .7rem; align-items: center; flex-wrap: wrap; margin-bottom: .6rem; }
label { font-weight: 600; }
select { font: inherit; padding: .3rem .5rem; border: 1px solid #adb1b8; border-radius: 6px; background: #f7f8fa; }
button { font: 600 14px system-ui; padding: .4rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
.info-row { font-size: .85rem; color: #555; margin-bottom: .6rem; min-height: 1.2em; font-family: ui-monospace, monospace; }
.race { display: grid; grid-template-columns: 1fr 1fr; gap: .7rem; margin-bottom: .7rem; }
.lane { border: 1px solid #cdd9e3; border-radius: 10px; padding: .6rem .8rem; background: #f7f8fa; }
.lane-title { font-weight: 700; font-size: .9rem; margin-bottom: .35rem; color: #1d3557; }
.lane-body { font-family: ui-monospace, monospace; font-size: .88rem; min-height: 1.5em; }
.lane-steps { font-size: .78rem; color: #666; margin-top: .3rem; min-height: 1em; }
.lane.winner { border-color: #0a7d33; background: #f0fff5; }
.lane.loser  { border-color: #adb1b8; }
.verdict { font-size: 1rem; font-weight: 700; min-height: 1.5em; }
.verdict.smooth { color: #c92f3c; }
.verdict.prime  { color: #0a7d33; }

// Code not found

Notice the pattern: when the order is smooth (all prime factors small), Pohlig-Hellman wins instantly by splitting the problem across tiny subgroups via the Chinese Remainder Theorem. When the order is a large prime, both methods struggle equally — and that is exactly the security assumption behind discrete-log cryptography.

Status: proven algorithm (Pohlig & Hellman, 1978). This is not an open problem — it is a settled, efficient attack with a tight runtime analysis.

The algorithm proceeds in three steps:

1. Factor the order. Write $n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$.
2. Solve in each prime-power subgroup. For each factor $p_i^{e_i}$, compute $x \bmod p_i^{e_i}$ using a baby-step giant-step approach inside the subgroup of order $p_i^{e_i}$. This costs $O(e_i(\log n + \sqrt{p_i}))$ group operations.
3. Combine with CRT. The system $x \equiv x_i \pmod{p_i^{e_i}}$ has a unique solution mod $n$ by the Chinese Remainder Theorem.

The total cost is $O\!\left(\sum_i e_i(\log n + \sqrt{p_i})\right)$ — dominated by $\sqrt{p_{\max}}$, the largest prime factor of the order. If $p_{\max}$ is small (smooth order), the whole thing is fast. If $p_{\max} \approx n$ (prime order), you gain nothing over baby-step giant-step on the full group.

This is why modern protocols use groups whose order is a safe prime $p = 2q + 1$ (so the only factors are 2 and the large prime $q$), or elliptic curve groups with prime order. Pohlig-Hellman made smooth-order groups obsolete overnight.

Compare with factoring: both problems underlie public-key cryptography, and both have unexpected algorithmic structure that practitioners must guard against.

Pohlig-Hellman is not a curiosity — it forced the entire field of public-key cryptography to tighten its parameter choices:

• Diffie-Hellman key exchange: the prime $p$ must be chosen so that $p-1$ has a large prime factor. The standard choice is a safe prime $p = 2q+1$ where $q$ is also prime. Using a smooth $p-1$ allows a passive eavesdropper to recover the shared secret in seconds.
• DSA and its variants: the group order $q$ in DSA is required to be a large prime, not just any divisor of $p-1$. This directly limits the Pohlig-Hellman attack to the subgroup of order $q$, which is hard.
• Elliptic-curve cryptography (ECC): curve designers verify that the curve order (number of points) has no small prime factors. Standard curves like P-256 and Curve25519 have prime or near-prime orders precisely to defeat this attack.
• Weak-key detection: CTF competitions and security audits routinely check whether a group order is smooth as a first step before attempting harder attacks.

Understanding Pohlig-Hellman also illuminates why discrete-log cryptography is more fragile than it looks: the hardness is not a property of the operation, but of the group you choose to work in.

Pohlig-Hellman is a masterclass in the gap between average-case hardness and worst-case hardness. The discrete logarithm is believed to be hard in general — but the algorithm shows that a single structural property of the group, its order being smooth, collapses the problem to something a pocket calculator can solve.

The Chinese Remainder Theorem is the engine: divide the secret among tiny subgroups, solve each piece independently, and glue the answer back together. Every step is polynomial; the bottleneck is the largest prime factor of the order, and if that factor is small, the bottleneck vanishes.

The practical legacy is permanent: safe primes, prime-order elliptic curves, and DSA's subgroup construction all exist because of what Pohlig and Hellman published in 1978. Choose the wrong group and discrete-log cryptography is not hard at all — it is merely disguised arithmetic.