Index Calculus

The discrete logarithm problem sits at the foundation of public-key cryptography: given a generator $g$, a prime $p$, and a value $h = g^x \bmod p$, find $x$. Going forward — raising $g$ 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 $h$. 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 $x$ 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 $L_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.

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

<p class="hint">{{hint}}</p>
<div class="row">
  <label>{{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">{{phase1_title}}</div>
    <div class="phase-desc">{{phase1_desc}}</div>
    <button id="btnRelation" type="button">{{btn_collect_one}}</button>
    <button id="btnCollectAll" type="button" class="ghost">{{btn_collect_all}}</button>
    <div id="relations" class="rel-list"></div>
    <div id="phase1status" class="pstatus"></div>
  </div>
  <div class="phase">
    <div class="phase-title">{{phase2_title}}</div>
    <div class="phase-desc">{{phase2_desc}}</div>
    <button id="btnIndiv" type="button" disabled>{{btn_indiv}}</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">{{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; }

// Code not found

Phase 1 — Relation collection: the algorithm picks random exponents $k$, computes $g^k \bmod p$, and checks whether the result factors completely over $B$. 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, 7$ known, pick a random $s$, compute $h \cdot g^s \bmod p$, and hope it is smooth too. If so, one equation gives $x + s$ in terms of known quantities, and $x$ falls out. Notice that phase 2 is fast once phase 1 has run — the expensive work is reusable across many targets for the same $p$ and $g$.

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

• Brute force tries every $x$ from $1$ to $p-1$: time $O(p)$, fully exponential in the bit-length of $p$.
• Baby-step giant-step (Shanks, 1971) reaches $O(\sqrt{p})$ using $O(\sqrt{p})$ space — still fully exponential in bit-length.
• Index calculus runs in $L_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 \approx 2^{512}$, the difference between $\sqrt{p}$ and $L_p[1/2]$ is staggering.
• Number Field Sieve (NFS) extends the idea with algebraic number fields, reaching $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 $10^{75}$ steps may fall to index calculus in $10^{20}$. That is why modern standards (RFC 3526, NIST SP 800-56A) require 2048-bit or larger groups.

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(\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 $p$ and $g$ (not on the target $h$), 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.

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.