Introduction

The discrete logarithm problem sits at the foundation of public-key cryptography: given a generator gg, a prime pp, and a value h=gx mod ph = g^x \bmod p, find xx. Going forward — raising gg to a power — is instant. Going backward is believed to be hard, and that asymmetry keeps key exchanges and digital signatures alive.

For decades the best known attack was brute force: try every exponent until you hit hh. With a 600-digit prime, that search has more steps than atoms in the universe. But index calculus does something far cleverer. Instead of searching for xx directly, it gathers a large collection of equations involving small primes — smooth numbers — and then solves a linear system. The result is an algorithm whose running time is sub-exponential, formally Lp[1/2,c]=ecln⁡pln⁡ln⁡pL_p[1/2, c] = e^{c\sqrt{\ln p \ln \ln p}} — vastly faster than brute force, though still not polynomial.

This is not a theoretical curiosity. Index calculus (and its descendants, the number field sieve variants) is the reason cryptographers abandoned 512-bit and 768-bit groups. Every time the recommended key length for finite-field Diffie–Hellman jumps, index calculus is somewhere in the story.

Try It

The demo below uses a small prime p=47p = 47 with generator g=5g = 5 and factor base B={2,3,5,7}B = \{2, 3, 5, 7\}. Pick any target h=gx mod 47h = g^x \bmod 47 and watch the two phases unfold.

<p class="hint">Index calculus on <b>p = 47</b>, <b>g = 5</b>, factor base <b>B = {2, 3, 5, 7}</b>. Pick a target exponent, collect smooth relations, then recover the discrete log.</p>
<div class="row">
  <label>Secret x = <b id="xv">9</b></label>
  <input id="xslider" type="range" min="1" max="45" value="9" />
  <div class="pub">h = 5<sup id="xe">9</sup> mod 47 = <b id="hv">—</b></div>
</div>
<div class="phases">
  <div class="phase">
    <div class="phase-title">Phase 1 — Relation Collection</div>
    <div class="phase-desc">Find exponents k where 5<sup>k</sup> mod 47 is B-smooth</div>
    <button id="btnRelation" type="button">Collect one relation</button>
    <button id="btnCollectAll" type="button" class="ghost">Collect all needed</button>
    <div id="relations" class="rel-list"></div>
    <div id="phase1status" class="pstatus"></div>
  </div>
  <div class="phase">
    <div class="phase-title">Phase 2 — Individual Log</div>
    <div class="phase-desc">Find s where h·5<sup>s</sup> mod 47 is B-smooth</div>
    <button id="btnIndiv" type="button" disabled>Find individual log</button>
    <div id="phase2out" class="rel-list"></div>
    <div id="phase2status" class="pstatus"></div>
  </div>
</div>
<div id="answer" class="answer"></div>
<button id="btnReset" type="button" class="ghost reset-btn">Reset</button>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.row { margin-bottom: .5rem; }
.row label { font: 600 13px system-ui; color: #1d3557; }
input[type=range] { width: 100%; margin: .3rem 0; accent-color: #457b9d; }
.pub { font: 700 13px ui-monospace, monospace; color: #1d3557; margin: .2rem 0; }
.pub b { color: #2a9d8f; }
.phases { display: grid; grid-template-columns: 1fr 1fr; gap: .7rem; margin: .5rem 0; }
@media (max-width: 480px) { .phases { grid-template-columns: 1fr; } }
.phase { border: 1px solid #d0d7de; border-radius: 10px; padding: .65rem; }
.phase-title { font: 700 12px system-ui; color: #457b9d; margin-bottom: .2rem; }
.phase-desc { font-size: .78rem; color: #666; margin-bottom: .45rem; line-height: 1.35; }
button { font: 600 13px system-ui; padding: .4rem .8rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; margin: .2rem .2rem .2rem 0; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }
.rel-list { margin-top: .4rem; font: 600 11px ui-monospace, monospace; color: #333;
            max-height: 120px; overflow-y: auto; }
.rel-list .rel { padding: 1px 0; border-bottom: 1px solid #f0f0f0; }
.rel-list .rel.new { color: #0a7d33; }
.pstatus { font: 600 12px system-ui; margin-top: .3rem; min-height: 1.2em; }
.pstatus.ok { color: #0a7d33; } .pstatus.info { color: #457b9d; } .pstatus.warn { color: #c0392b; }
.answer { font: 700 15px system-ui; margin: .5rem 0; min-height: 1.5em; padding: .4rem .7rem;
          border-radius: 8px; }
.answer.ok { background: #eafaf1; color: #0a7d33; border: 1px solid #b7e4c7; }
.answer.bad { background: #fdf2f2; color: #c0392b; border: 1px solid #f5c2c7; }
.reset-btn { margin-top: .3rem; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Index Calculus demo — p=47, g=5, factor base B={2,3,5,7}
// Phase 1: find k such that g^k mod p is B-smooth, record (k, e2, e3, e5, e7)
//   i.e. g^k ≡ 2^e2 * 3^e3 * 5^e5 * 7^e7  (mod p)
//   => k * log(g) ≡ e2*log(2) + e3*log(3) + e5*log(5) + e7*log(7) (mod p-1)
//   Since g=5, log_g(g)=1, and log_g(5)=1 by definition.
// Phase 2: find s such that h*g^s mod p is B-smooth, then recover x.
// We solve the linear system mod (p-1)=46 with Gaussian elimination.

const P = 47, G = 5, ORDER = 46;
const BASE = [2, 3, 5, 7];

function modpow(b, e, m) {
  let r = 1n; b = BigInt(b) % BigInt(m); e = BigInt(e); m = BigInt(m);
  while (e > 0n) { if (e & 1n) r = r * b % m; b = b * b % m; e >>= 1n; }
  return Number(r);
}

function trySmoothFactor(n, base) {
  // Returns exponent vector if n is base-smooth, else null
  let x = n;
  const exps = base.map(() => 0);
  for (let i = 0; i < base.length; i++) {
    while (x % base[i] === 0) { exps[i]++; x = Math.floor(x / base[i]); }
  }
  return x === 1 ? exps : null;
}

// Precompute all smooth k in [1, ORDER-1] for phase 1 and phase 2
const allPhase1 = [];
for (let k = 1; k < ORDER; k++) {
  const val = modpow(G, k, P);
  const exps = trySmoothFactor(val, BASE);
  if (exps) allPhase1.push({ k, val, exps });
}

// Modular inverse via extended Euclidean (mod must be prime or coprime)
function modInv(a, m) {
  let [old_r, r] = [a, m], [old_s, s] = [1, 0];
  while (r !== 0) {
    const q = Math.floor(old_r / r);
    [old_r, r] = [r, old_r - q * r];
    [old_s, s] = [s, old_s - q * s];
  }
  return ((old_s % m) + m) % m;
}

// Solve linear system Ax = b mod n using Gaussian elimination
// Returns solution vector or null
function solveModular(equations, n) {
  // equations: array of {coeffs:[4 nums], rhs:num}
  // unknowns: [log2, log3, log5, log7]
  const numVars = 4;
  const mat = equations.map(eq => [...eq.coeffs.map(c => ((c % n) + n) % n), ((eq.rhs % n) + n) % n]);
  const rows = mat.length;
  const pivotRow = new Array(numVars).fill(-1);

  let col = 0, row = 0;
  while (col < numVars && row < rows) {
    // Find pivot
    let pivot = -1;
    for (let r = row; r < rows; r++) {
      if (mat[r][col] !== 0) {
        // Check if pivot is invertible mod n
        let g = gcd(mat[r][col], n);
        if (g === 1) { pivot = r; break; }
      }
    }
    if (pivot === -1) { col++; continue; }
    // Swap
    [mat[row], mat[pivot]] = [mat[pivot], mat[row]];
    pivotRow[col] = row;
    const inv = modInv(mat[row][col], n);
    // Scale pivot row
    for (let c = 0; c <= numVars; c++) mat[row][c] = (mat[row][c] * inv) % n;
    // Eliminate
    for (let r = 0; r < rows; r++) {
      if (r === row || mat[r][col] === 0) continue;
      const factor = mat[r][col];
      for (let c = 0; c <= numVars; c++) mat[r][c] = ((mat[r][c] - factor * mat[row][c]) % n + n) % n;
    }
    row++; col++;
  }

  // Extract solution
  const sol = new Array(numVars).fill(-1);
  for (let c = 0; c < numVars; c++) {
    if (pivotRow[c] === -1) continue;
    const r = pivotRow[c];
    // rhs should be the answer for this variable
    let found = true;
    for (let cc = 0; cc < numVars; cc++) {
      if (cc !== c && mat[r][cc] !== 0) { found = false; break; }
    }
    if (found) sol[c] = mat[r][numVars];
  }
  return sol;
}

function gcd(a, b) { return b === 0 ? a : gcd(b, a % b); }

// State
let secretX = 9;
let collectedRelations = [];
let baseLogsSolved = null; // [log2, log3, log5, log7] mod ORDER

function computeH() { return modpow(G, secretX, P); }

function render() {
  const h = computeH();
  document.getElementById('xv').textContent = secretX;
  document.getElementById('xe').textContent = secretX;
  document.getElementById('hv').textContent = h;
}

function renderRelations() {
  const el = document.getElementById('relations');
  if (collectedRelations.length === 0) { el.innerHTML = ''; return; }
  el.innerHTML = collectedRelations.map((r, i) => {
    const parts = r.exps.map((e, j) => e ? BASE[j] + (e > 1 ? '^' + e : '') : null).filter(Boolean).join('·');
    return `<div class="rel${i === collectedRelations.length - 1 ? ' new' : ''}">` +
      `k=${r.k}: 5^${r.k}≡${r.val}=${parts}</div>`;
  }).join('');
  el.scrollTop = el.scrollHeight;
}

function tryCollectOne() {
  // Find next unused smooth k
  const usedK = new Set(collectedRelations.map(r => r.k));
  const next = allPhase1.find(r => !usedK.has(r.k));
  if (!next) {
    setStatus('phase1status', 'No more smooth relations available!', 'warn');
    return;
  }
  collectedRelations.push(next);
  renderRelations();
  setStatus('phase1status', fmt('Found: 5^%k% ≡ %val% mod 47 (smooth!)', { k: next.k, val: next.val }), 'ok');
  attemptSolve();
}

function collectAll() {
  const usedK = new Set(collectedRelations.map(r => r.k));
  for (const r of allPhase1) {
    if (!usedK.has(r.k)) collectedRelations.push(r);
  }
  renderRelations();
  setStatus('phase1status', fmt('Collected %length% smooth relations.', { length: collectedRelations.length }), 'ok');
  attemptSolve();
}

function attemptSolve() {
  if (collectedRelations.length < 4) {
    setStatus('phase1status', fmt('%length% relation(s) — need at least 4 to solve.', { length: collectedRelations.length }), 'info');
    return;
  }
  // Build equations: k ≡ e2*L2 + e3*L3 + e5*L5 + e7*L7 (mod ORDER)
  // where Li = log_g(base[i])
  // But log_g(g) = log_g(5) = 1, so for base[2]=5: L5 = 1 known.
  // We can substitute: equation becomes k - e5*1 ≡ e2*L2 + e3*L3 + e7*L7 (mod ORDER)
  // Actually let's keep all 4 unknowns L2,L3,L5,L7 and add the equation L5 = 1.
  const equations = collectedRelations.map(r => ({
    coeffs: r.exps.slice(), // [e2, e3, e5, e7]
    rhs: r.k
  }));
  // Add known: L5 = 1 (since g = 5)
  equations.push({ coeffs: [0, 0, 1, 0], rhs: 1 });

  const sol = solveModular(equations, ORDER);
  if (sol.every(v => v !== -1)) {
    baseLogsSolved = sol;
    setStatus('phase1status',
      fmt('✓ Solved: log(2)=%v%, log(3)=%v2%, log(5)=%v3%, log(7)=%v4% (mod 46)', { v: sol[0], v2: sol[1], v3: sol[2], v4: sol[3] }), 'ok');
    document.getElementById('btnIndiv').disabled = false;
  } else {
    setStatus('phase1status',
      fmt('%length% relation(s) collected — system not yet fully determined. Collect more.', { length: collectedRelations.length }), 'info');
  }
}

function findIndividualLog() {
  if (!baseLogsSolved) return;
  const h = computeH();
  // Try s in [0, ORDER-1]: compute h * g^s mod p, check smooth
  const p2el = document.getElementById('phase2out');
  p2el.innerHTML = '';
  for (let s = 0; s < ORDER; s++) {
    const val = (h * modpow(G, s, P)) % P;
    const exps = trySmoothFactor(val, BASE);
    if (exps) {
      // h * g^s ≡ 2^e2 * 3^e3 * 5^e5 * 7^e7 (mod p)
      // => log(h) + s ≡ e2*L2 + e3*L3 + e5*L5 + e7*L7 (mod ORDER)
      // => x = log(h) ≡ (e2*L2 + e3*L3 + e5*L5 + e7*L7 - s) mod ORDER
      const rhs = exps.reduce((acc, e, i) => acc + e * baseLogsSolved[i], 0);
      const x = ((rhs - s) % ORDER + ORDER) % ORDER;
      const parts = exps.map((e, j) => e ? BASE[j] + (e > 1 ? '^' + e : '') : null).filter(Boolean).join('·');
      p2el.innerHTML = `<div class="rel new">s=${s}: h·5^${s}≡${val}=${parts}</div>` +
        `<div class="rel">x+${s} ≡ ${rhs % ORDER} (mod 46) → x = ${x}</div>`;
      setStatus('phase2status', fmt('✓ Found x = %x% after trying s=0..%s%', { x: x, s: s }), 'ok');

      // Verify
      const check = modpow(G, x, P);
      const ans = document.getElementById('answer');
      if (check === h) {
        ans.className = 'answer ok';
        ans.textContent = fmt('✓ 5^%x% mod 47 = %check% = h  — discrete log recovered! (true x = %secretX%)', { x: x, check: check, secretX: secretX });
      } else {
        ans.className = 'answer bad';
        ans.textContent = fmt('✗ Got x=%x% but 5^%x% mod 47 = %check% ≠ %h%. Try collecting more relations.', { x: x, check: check, h: h });
      }
      return;
    }
  }
  setStatus('phase2status', 'No smooth h·g^s found — unexpected for p=47.', 'warn');
}

function setStatus(id, msg, cls) {
  const el = document.getElementById(id);
  el.textContent = msg; el.className = 'pstatus ' + (cls || '');
}

function reset() {
  collectedRelations = [];
  baseLogsSolved = null;
  document.getElementById('relations').innerHTML = '';
  document.getElementById('phase2out').innerHTML = '';
  document.getElementById('answer').className = 'answer';
  document.getElementById('answer').textContent = '';
  setStatus('phase1status', '', '');
  setStatus('phase2status', '', '');
  document.getElementById('btnIndiv').disabled = true;
}

document.getElementById('xslider').addEventListener('input', function () {
  secretX = +this.value; render(); reset();
});
document.getElementById('btnRelation').addEventListener('click', tryCollectOne);
document.getElementById('btnCollectAll').addEventListener('click', collectAll);
document.getElementById('btnIndiv').addEventListener('click', findIndividualLog);
document.getElementById('btnReset').addEventListener('click', reset);

render();
Result
Console

Phase 1 — Relation collection: the algorithm picks random exponents kk, computes gk mod pg^k \bmod p, and checks whether the result factors completely over BB. Each success gives a linear equation in the unknown discrete logs of the small primes. Once enough smooth relations are collected, the system is solvable.

Phase 2 — Individual log: with the logs of 2,3,5,72, 3, 5, 7 known, pick a random ss, compute h⋅gs mod ph \cdot g^s \bmod p, and hope it is smooth too. If so, one equation gives x+sx + s in terms of known quantities, and xx falls out. Notice that phase 2 is fast once phase 1 has run — the expensive work is reusable across many targets for the same pp and gg.

The Real Complexity

What does sub-exponential actually mean, and why does it matter?

  • Brute force tries every xx from 11 to p−1p-1: time O(p)O(p), fully exponential in the bit-length of pp.
  • Baby-step giant-step (Shanks, 1971) reaches O(p)O(\sqrt{p}) using O(p)O(\sqrt{p}) space — still fully exponential in bit-length.
  • Index calculus runs in Lp[1/2,c]=e(c+o(1))ln⁡p⋅ln⁡ln⁡pL_p[1/2, c] = e^{(c+o(1))\sqrt{\ln p \cdot \ln \ln p}}. This is sub-exponential but super-polynomial: it grows faster than any polynomial yet slower than any exponential. For p≈2512p \approx 2^{512}, the difference between p\sqrt{p} and Lp[1/2]L_p[1/2] is staggering.
  • Number Field Sieve (NFS) extends the idea with algebraic number fields, reaching Lp[1/3,(64/9)1/3]L_p[1/3, (64/9)^{1/3}] — a further enormous speedup. NFS is the current state of the art for large finite-field discrete log.
  • Current status: no polynomial-time classical algorithm for discrete log in finite fields is known. The problem is believed hard but not proven so — just like P vs NP. Shor's quantum algorithm (1994) would solve it in polynomial time on a large-enough quantum computer.

The key lesson: index calculus does not break discrete log — it reshapes the security landscape. A group where brute force needs 107510^{75} steps may fall to index calculus in 102010^{20}. That is why modern standards (RFC 3526, NIST SP 800-56A) require 2048-bit or larger groups.

Where It Matters

Index calculus is not a classroom exercise — it drives real-world cryptographic decisions every day:

  • Diffie–Hellman and DSA key sizes: every recommended minimum group size (1024 → 2048 → 3072 bits) is a direct response to the improving state of index calculus and NFS implementations.
  • The Logjam attack (2015): researchers showed that many TLS servers still negotiated 512-bit Diffie–Hellman parameters. A precomputed NFS run against the handful of commonly used 512-bit primes let attackers downgrade and break connections in real time. The root cause was index calculus.
  • The shift to elliptic curves: index calculus does not extend naturally to generic elliptic curve groups. The best known discrete-log algorithms on elliptic curves are still fully exponential (O(p)O(\sqrt{p})). That gap is precisely why ECDH and ECDSA dominate modern TLS — a 256-bit elliptic curve key matches the security of a 3072-bit finite-field key.
  • Precomputation reuse: because phase 1 of index calculus depends only on pp and gg (not on the target hh), an attacker who precomputes the factor-base logs once can crack any target for that group almost instantly. This is why reusing standardized "well-known" primes is dangerous.

Understand index calculus and you understand why key sizes matter, why elliptic curves won, and why the discrete log problem is not one monolithic assumption but a family of problems with very different concrete hardness.

Conclusion

Index calculus is one of the most elegant ideas in algorithmic number theory: instead of searching for a discrete log directly, collect cheap clues about small primes and let linear algebra finish the job. The result is sub-exponential time — not polynomial, but enough to force the entire field of cryptography to keep raising the bar on key sizes.

The story does not end there. Every decade a new variant — the quadratic sieve, the number field sieve, the function field sieve — shaves another factor off the exponent. Meanwhile, the promise of Shor's algorithm looms: a large quantum computer would dissolve the discrete log problem entirely, which is why post-quantum cryptography is racing to replace finite-field assumptions with problems like lattice SVP where no index-calculus-style shortcut is yet known.

Share this article

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

Comments

Loading comments...

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