Index Calculus — sub-exponential DLP attack for large prime fields with no smooth structure

Index calculus is a sub-exponential algorithm for the discrete logarithm g^x = h in the multiplicative group of a finite field (F_p^*, or F_{p^k}^*), used when the group order has a large prime factor and no smooth/special structure to exploit — it is the "everything else has failed" tool for large prime-field DLP.

The signal that betrays it

You're staring at index calculus, not Baby-Step Giant-Step — the generic meet-in-the-middle solver for a mid-sized discrete log or Pohlig-Hellman — solving the discrete log when the group order is smooth, when:

- The modulus p (or field size) is hundreds of bits, and p - 1 (or the relevant group order) has been checked and does not factor into small primes — see Smooth Numbers — the concept behind why Pollard p-1, Pohlig-Hellman, and index calculus work (and when they don't). If it were smooth, Pohlig-Hellman — solving the discrete log when the group order is smooth would already have solved it cheaply. - The group is a prime field, F_p^* or an extension F_{p^k}^* — not a generic elliptic curve group. This distinction matters: index calculus relies on a factor base of "small primes," a notion that exists for integers/polynomials but has no efficient analogue for a generic elliptic curve's points, so it does not transfer to Elliptic Curve Discrete Logarithm Problem — the curve order's factorization picks your attack the way it does across finite fields (see "What does NOT work" below). - Direct O(sqrt(n)) methods are visibly out of reach: for n in the hundreds-of-bits range, sqrt(n) is astronomically larger than anything BSGS/Pollard rho can hold in memory or iterate over in reasonable time. - Field-tested threshold (public benchmark, not just theory): in practice, generic methods (Pohlig-Hellman combined with Pollard rho/BSGS, as used by Sage's default discrete_log) stay usable only up to roughly N < 10^30. Index calculus (PARI/GP's znlog, a linear-sieve implementation) extends that reach substantially — how far depends on the field's structure and how much compute is thrown at it, not a single fixed bit-count: fully worked academic computations using index-calculus variants (NFS-DL, function field sieve) have solved discrete logs at 795-bit (a prime field, Dec 2019), 1051-bit (a field of 22-bit characteristic, via function field sieve), and 4841-bit (a characteristic-3 field, 2016) — see Wikipedia's discrete logarithm records. A CTF's znlog/Sage call, run interactively rather than as a multi-week distributed computation, will land well short of those academic records, but there is no fixed bit-count past which "index calculus stops working" — treat sluggishness as a cue to check whether the challenge wants a different weakness (see below), not as evidence you've hit an algorithmic ceiling.

How it's exploited

1. Pick a factor base: all primes up to a bound B. B trades off relation-finding cost against linear-algebra cost — this is the parameter every real implementation tunes automatically, so in a CTF you almost never choose it by hand. 2. Collect smooth relations: find exponents k such that g^k mod p factors completely over the factor base, g^k = prod p_i^{e_i}. Each relation is one linear equation in the unknown logs log_g(p_i). Keep collecting until you have more relations than factor-base primes. 3. Solve the linear system for log_g(p_i) for every prime in the factor base. This is *not* an ordinary GF(2) system — it's solved modulo the group order n (or modulo each prime-power factor of n), which is why real tooling, not a hand-rolled solver, is the right move; see Linear Algebra over GF(2) — solving bit-level unknowns as a linear system mod 2 for the analogous but distinct GF(2) elimination technique used elsewhere in this wiki (LFSR/CRC/Hill-cipher recovery). 4. Solve for the target: search for an exponent s such that h * g^s is itself smooth over the factor base; once you have that factorization, the known per-prime logs combine to give log_g(h). 5. In practice, invoke a library — do not hand-roll steps 1-4. In CTF conditions: - Sage's discrete_log(F(h), F(g)) auto-selects the right algorithm and will pick index calculus for large F_p. - PARI/GP's znlog(h, g) is the concrete linear-sieve index-calculus implementation and is the one to reach for by name when you need to go past what Sage's generic path handles, or when you're scripting outside Sage. - znlog internally runs Pohlig-Hellman — solving the discrete log when the group order is smooth first to peel off any smooth part of the order, *then* falls back to index calculus for what remains — so in a mixed-order group you often get PH-then-index-calculus for free from one function call rather than having to chain them yourself. - For genuinely huge/special fields beyond what a general-purpose library handles well, dedicated GNFS-DL (general number field sieve for discrete log) tooling is the escalation path, though this is rarely what a CTF expects. 6. Always verify g^x == h at the end (or g^x == h mod (subgroup order) if you solved in a subgroup) — cheap and catches an off-by-relation error in the linear algebra before you waste time debugging downstream.

Background/related: Discrete Logarithm — the factorization of the group order picks your algorithm (the triage hub — read this first to confirm index calculus is actually the right branch), Pohlig-Hellman — solving the discrete log when the group order is smooth (try this first if the order might be smooth), Baby-Step Giant-Step — the generic meet-in-the-middle solver for a mid-sized discrete log (try this first if the order/subgroup is small), Smooth Numbers — the concept behind why Pollard p-1, Pohlig-Hellman, and index calculus work (and when they don't) (the concept that both defines the factor base and explains why the algorithm terminates), Chinese Remainder Theorem — recombining residues across coprime moduli (used inside the PH pre-processing step).

What does NOT work

- Reaching for index calculus before checking smoothness. If p - 1 (or the relevant order) turns out to be smooth, Pohlig-Hellman — solving the discrete log when the group order is smooth solves the problem in a fraction of the time — always factor the order first. Index calculus is the fallback for when that factorization comes back with a large prime factor, not the default first move. - Generic O(sqrt(n)) methods once `n` is genuinely large. Baby-Step Giant-Step — the generic meet-in-the-middle solver for a mid-sized discrete log and Pollard's rho are the right tools for medium orders, but they simply do not scale to a hundreds-of-bits prime field order — the sqrt(n) table/iteration count becomes infeasible well before index calculus's sub-exponential cost does. Don't burn a challenge's time budget on BSGS "just in case" once you've confirmed the order is large and non-smooth. - Porting index calculus to a generic elliptic curve group. This is the field's own stated boundary, not just a CTF quirk: elliptic curve points have no efficient notion of "small prime" elements to build a factor base from, so the relation-collection step that makes index calculus sub-exponential for F_p^* has no analogue for a generic curve. If the challenge is ECC-flavored, this is a signal to pivot to Elliptic Curve Discrete Logarithm Problem — the curve order's factorization picks your attack's own attack family (e.g. Smart Attack — the anomalous-curve signal that turns ECDLP into polynomial time for anomalous curves, generic BSGS/rho otherwise) rather than trying to force index calculus onto curve points. - Hand-rolling the linear-algebra step as a naive GF(2) solve. The relation matrix here is solved modulo the group order (or a prime-power factor of it), not modulo 2 — treating it as a GF(2) linear system (the pattern that works for LFSR/CRC recovery elsewhere in this wiki) silently gives wrong logs. Use library tooling (Sage/PARI) that solves the correct modulus, or explicitly track which modulus you're solving over if you must do it by hand. - Assuming `znlog`/Sage stalling means you've hit index calculus's hard ceiling. Index calculus itself has no fixed bit-count wall — academic computations using its variants (NFS-DL, function field sieve) have solved discrete logs at 795-bit, 1051-bit, and even 4841-bit fields (see Wikipedia's discrete logarithm records), far beyond any single CTF-timescale figure. What a CTF's znlog/Sage call can chew through *interactively* is a much smaller, tooling/time-budget bound, not the algorithm's actual reach. If it's grinding forever on a CTF-sized field, that's still a strong hint the intended path is a weakened parameter elsewhere (leaked partial exponent, small subgroup, bad randomness) rather than that more compute on a naive run will save you — but don't cite a specific bit-count as "proof" you're past index calculus's range.