Introduction

Public-key cryptography rests on a simple-sounding question: given gx mod pg^x \bmod p, find xx. 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 ⁣(∑iei(log⁡n+pi))O\!\left(\sum_i e_i \left(\log n + \sqrt{p_i}\right)\right), where n=∏piein = \prod p_i^{e_i} is the group order. When every pip_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.

Try It: Smooth-Order Weakness

Choose a group order and a generator. The demo computes gx mod pg^x \bmod p for a random secret xx, 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">
  Pick a group configuration. The demo hides a secret exponent <b>x</b> and
computes <b>h = g<sup>x</sup> mod p</b>. Then it races <b>Brute Force</b>
against <b>Pohlig-Hellman</b> to recover x from h.
</p>
<div class="controls">
  <label>Group preset:
    <select id="preset">
      <option value="smooth16">Smooth order (16 = 2⁴) — p=17</option>
      <option value="smooth120">Smooth order (120 = 2³·3·5) — p=241</option>
      <option value="prime23">Prime-order subgroup (23) — p=47</option>
      <option value="prime53">Prime-order subgroup (53) — p=107</option>
    </select>
  </label>
  <button id="runBtn" type="button">Run Race</button>
</div>
<div class="info-row" id="groupInfo"></div>
<div class="race">
  <div class="lane" id="laneA">
    <div class="lane-title">Brute Force</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">Pohlig-Hellman</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Pohlig-Hellman demo: shows how smooth group orders make discrete log easy.
// All arithmetic is done with plain JS numbers (safe for the small groups used).
// No imports — pure vanilla JS.

// --- Modular arithmetic helpers ---
function modpow(base, exp, mod) {
  let result = 1n;
  base = BigInt(base) % BigInt(mod);
  exp = BigInt(exp);
  mod = BigInt(mod);
  while (exp > 0n) {
    if (exp & 1n) result = result * base % mod;
    base = base * base % mod;
    exp >>= 1n;
  }
  return Number(result);
}

function modInverse(a, m) {
  // Extended Euclidean algorithm
  let [old_r, r] = [BigInt(a), BigInt(m)];
  let [old_s, s] = [1n, 0n];
  while (r !== 0n) {
    const q = old_r / r;
    [old_r, r] = [r, old_r - q * r];
    [old_s, s] = [s, old_s - q * s];
  }
  return Number(((old_s % BigInt(m)) + BigInt(m)) % BigInt(m));
}

// Factor n into prime-power pairs [[p,e], ...]
function factorize(n) {
  const factors = [];
  let rem = n;
  for (let p = 2; p * p <= rem; p++) {
    if (rem % p === 0) {
      let e = 0;
      while (rem % p === 0) { e++; rem = Math.floor(rem / p); }
      factors.push([p, e]);
    }
  }
  if (rem > 1) factors.push([rem, 1]);
  return factors;
}

// Baby-step giant-step: find x in [0, n) s.t. g^x = h (mod p)
function babyGiant(g, h, n, p) {
  const m = Math.ceil(Math.sqrt(n)) + 1;
  const table = new Map();
  let baby = 1;
  for (let j = 0; j < m; j++) {
    table.set(baby, j);
    baby = Number(BigInt(baby) * BigInt(g) % BigInt(p));
  }
  const gm = modpow(modInverse(g, p), m, p); // g^{-m} mod p
  let giant = h;
  for (let i = 0; i < m; i++) {
    if (table.has(giant)) {
      const x = i * m + table.get(giant);
      if (x < n) return x;
    }
    giant = Number(BigInt(giant) * BigInt(gm) % BigInt(p));
  }
  return -1;
}

// CRT: combine residues x_i mod m_i  →  x mod lcm
function crt(residues, moduli) {
  let x = BigInt(residues[0]);
  let m = BigInt(moduli[0]);
  for (let i = 1; i < residues.length; i++) {
    const xi = BigInt(residues[i]);
    const mi = BigInt(moduli[i]);
    // x + m*t ≡ xi (mod mi)  →  t ≡ (xi - x) * m^{-1} (mod mi)
    const inv = BigInt(modInverse(Number(m % mi), Number(mi)));
    const t = ((xi - x % mi) * inv % mi + mi) % mi;
    x = x + m * t;
    m = m * mi;
  }
  return Number(x % m);
}

// Pohlig-Hellman: solve g^x = h (mod p) given order n = prod p_i^e_i
function pohligHellman(g, h, n, p, factors, log) {
  const residues = [];
  const moduli = [];
  for (const [pi, ei] of factors) {
    const qi = Math.pow(pi, ei);  // p_i^e_i
    // Generator and target for the subgroup of order qi
    const gi = modpow(g, Math.floor(n / qi), p);
    const hi = modpow(h, Math.floor(n / qi), p);
    log("  " + fmt(`Subgroup order %qi% (%pi%^%ei%): solve g_i^x = h_i (mod p)`, { qi: qi, pi: pi, ei: ei }));
    const xi = babyGiant(gi, hi, qi, p);
    log(`    → x ≡ ${xi} (mod ${qi})`);
    residues.push(xi);
    moduli.push(qi);
  }
  log("  " + fmt(`CRT combine: %map%`, { map: residues.map((r,i) => `x≡${r}(mod${moduli[i]})`).join(', ') }));
  return crt(residues, moduli);
}

// Brute force: try x = 0,1,2,... until g^x = h (mod p)
function bruteForce(g, h, n, p, log) {
  let cur = 1;
  for (let x = 0; x < n; x++) {
    if (cur === h) { log("  " + fmt(`Tried %x% values`, { x: x })); return x; }
    cur = Number(BigInt(cur) * BigInt(g) % BigInt(p));
  }
  return -1;
}

// --- Presets (verified: g has exact order n in Z/pZ*) ---
// smooth16:  p=17,  g=3, ord(g)=16=2^4        (very smooth)
// smooth120: p=241, g=3, ord(g)=120=2^3·3·5   (smooth)
// prime23:   p=47,  g=2, ord(g)=23             (prime-order subgroup of safe prime 47=2·23+1)
// prime53:   p=107, g=3, ord(g)=53             (prime-order subgroup of safe prime 107=2·53+1)
const PRESET_MAP = {
  smooth16:  { p: 17,  g: 3,  n: 16,  desc: `order 16 = 2⁴ (very smooth)` },
  smooth120: { p: 241, g: 3,  n: 120, desc: `order 120 = 2³·3·5 (smooth)` },
  prime23:   { p: 47,  g: 2,  n: 23,  desc: `order 23 (prime — hard)` },
  prime53:   { p: 107, g: 3,  n: 53,  desc: `order 53 (prime — hard)` },
};

function run() {
  const key = document.getElementById('preset').value;
  // map old key ’prime101’ to ’prime53’ for safety
  const preset = PRESET_MAP[key] || PRESET_MAP['prime53'];
  const { p, g, n } = preset;

  // Pick random secret x in [1, n-1]
  const x = 1 + Math.floor(Math.random() * (n - 1));
  const h = modpow(g, x, p);
  const factors = factorize(n);
  const isSmooth = factors.every(([pi]) => pi <= 11);

  document.getElementById('groupInfo').textContent =
    fmt(`p=%p%, g=%g%, order n=%n% (%map%)  |  secret x=%x%  |  h = g^x mod p = %h%`, { p: p, g: g, n: n, map: factors.map(([pi,ei])=>ei>1?`${pi}^${ei}`:pi).join('·'), x: x, h: h });

  // Brute force
  const bfLogs = [];
  const t0 = performance.now();
  const bfAns = bruteForce(g, h, n, p, s => bfLogs.push(s));
  const t1 = performance.now();
  document.getElementById('bodyA').textContent =
    bfAns === x ? `✓ x = ${bfAns}` : fmt(`✗ got %bfAns%`, { bfAns: bfAns });
  document.getElementById('stepsA').textContent =
    fmt(`%bfLogs%
Time: %v% ms`, { bfLogs: bfLogs.join('\n'), v: (t1-t0).toFixed(2) });

  // Pohlig-Hellman
  const phLogs = [];
  const t2 = performance.now();
  const phAns = pohligHellman(g, h, n, p, factors, s => phLogs.push(s));
  const t3 = performance.now();
  document.getElementById('bodyB').textContent =
    phAns === x ? `✓ x = ${phAns}` : fmt(`✗ got %phAns%`, { phAns: phAns });
  document.getElementById('stepsB').textContent =
    fmt(`%phLogs%
Time: %v% ms`, { phLogs: phLogs.join('\n'), v: (t3-t2).toFixed(2) });

  // Winner styling
  const laneA = document.getElementById('laneA');
  const laneB = document.getElementById('laneB');
  const verdict = document.getElementById('verdict');
  if (isSmooth) {
    laneB.className = 'lane winner';
    laneA.className = 'lane loser';
    verdict.textContent = `Smooth order → Pohlig-Hellman dominates! Each subgroup is tiny.`;
    verdict.className = 'verdict smooth';
  } else {
    laneA.className = 'lane';
    laneB.className = 'lane';
    verdict.textContent = `Large prime factor → no speedup. Both methods work the full group.`;
    verdict.className = 'verdict prime';
  }
}

document.getElementById('runBtn').addEventListener('click', run);
run();
Result
Console

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.

The Real Complexity

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=p1e1p2e2⋯pkekn = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}.
  2. Solve in each prime-power subgroup. For each factor pieip_i^{e_i}, compute x mod pieix \bmod p_i^{e_i} using a baby-step giant-step approach inside the subgroup of order pieip_i^{e_i}. This costs O(ei(log⁡n+pi))O(e_i(\log n + \sqrt{p_i})) group operations.
  3. Combine with CRT. The system x≡xi(modpiei)x \equiv x_i \pmod{p_i^{e_i}} has a unique solution mod nn by the Chinese Remainder Theorem.

The total cost is O ⁣(∑iei(log⁡n+pi))O\!\left(\sum_i e_i(\log n + \sqrt{p_i})\right) — dominated by pmax⁡\sqrt{p_{\max}}, the largest prime factor of the order. If pmax⁡p_{\max} is small (smooth order), the whole thing is fast. If pmax⁡≈np_{\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+1p = 2q + 1 (so the only factors are 2 and the large prime qq), 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.

Where It Matters

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 pp must be chosen so that p−1p-1 has a large prime factor. The standard choice is a safe prime p=2q+1p = 2q+1 where qq is also prime. Using a smooth p−1p-1 allows a passive eavesdropper to recover the shared secret in seconds.
  • DSA and its variants: the group order qq in DSA is required to be a large prime, not just any divisor of p−1p-1. This directly limits the Pohlig-Hellman attack to the subgroup of order qq, 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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/pohlig-hellman/Content licensed under CC BY-NC 4.0.