Discrete Logarithm — the factorization of the group order picks your algorithm

The discrete logarithm problem (DLP) asks for x such that g^x = h in a finite cyclic group of order n — a multiplicative group mod a prime, an elliptic curve, any group where you can multiply and compare elements. Its assumed hardness underpins Diffie-Hellman, DSA, and ElGamal.

The signal that gives it away

You see a generator g, a public value h (or y, or Q), a modulus or curve, and you're asked to recover an exponent, a private key, or a scalar k such that Q = k*P. Any DH/DSA/ElGamal/ECDH/ECDSA-flavored challenge that doesn't fall to a simpler trick (nonce reuse, leaked bits, protocol logic — see Key-Exchange Methodology — triage any DH/ECDH challenge before reaching for heavy DLP machinery) eventually reduces to this. CTF setups almost never present a genuinely hard instance: they weaken one parameter, and the weakness shows up entirely in the factorization of the group order. Step zero, before touching any algorithm, is always: compute n (the order of g, not blindly p-1 or the full curve order) and factor it. The factorization dictates everything downstream.

How to exploit it

Triage by the shape of factor(n):

1. `n` small (roughly ≤ 2^40–2^48, so sqrt(n) table entries fit in memory): direct Baby-Step Giant-Step — the generic meet-in-the-middle solver for a mid-sized discrete log, O(sqrt(n)) time and space, meet-in-the-middle. If memory is the bottleneck rather than time, switch to Pollard's rho for logs — same O(sqrt(n)) time, O(1) space. 2. `n` smooth (only small prime-power factors, even if `n` itself is astronomically large): Pohlig-Hellman — solving the discrete log when the group order is smooth — solve the tiny DLP inside each prime-power subgroup, recombine with Chinese Remainder Theorem — recombining residues across coprime moduli. This is the classic "the modulus is prime but p-1 (or the curve order) is smooth" trap, and by far the most common intended path in a CTF DH/ElGamal challenge: check smoothness before anything else. 3. `n` has one large residual prime factor after peeling off the smooth part: run Pohlig-Hellman on the smooth factors, then finish the remaining large-prime sub-DLP with Index Calculus — sub-exponential DLP attack for large prime fields with no smooth structure (multiplicative groups of finite fields only) or brute-force/rho if it's still small enough. 4. Large prime-field DLP with no smoothness or special structure at all: Index Calculus — sub-exponential DLP attack for large prime fields with no smooth structure, sub-exponential — the realistic attack once p is hundreds of bits and Pohlig-Hellman/BSGS are both infeasible. In practice you invoke a library (Pari/GP znlog, a GNFS-DL tool) rather than hand-roll it; index calculus does not extend to generic elliptic curve groups, which is precisely why ECC gets away with much smaller key sizes for equivalent security. 5. Elliptic curve, anomalous order (`#E(F_p) == p`): Smart Attack — the anomalous-curve signal that turns ECDLP into polynomial time solves it in linear time via a p-adic lift — always check the curve order against p first, since anomalous parameters are often disguised as ordinary-looking large numbers. 6. Elliptic curve, singular (discriminant zero): reduces to an easy additive/multiplicative field DLP; see the curve-fundamentals triage.

``python from sage.all import GF, discrete_log F = GF(p); g = F(g); h = F(h) n = g.multiplicative_order() # the actual subgroup order, not p-1 x = discrete_log(h, g, ord=n) # Sage auto-picks BSGS/Pohlig-Hellman/index-calculus assert g**x == h # always verify before trusting the result ``

Sage's discrete_log (and factor(n) up front) will usually settle the whole decision tree for you in one call — but knowing which branch it silently picked is what tells you whether to trust a slow run or suspect you fed it the wrong subgroup order.

What does NOT work

- Running BSGS or brute force against a large prime-order `n` because "it's generic and should just work." It doesn't — O(sqrt(n)) is only tractable up to ~2^40–2^48; beyond that the table (or the rho walk) simply never finishes in a CTF's timeframe. If factor(n) shows a large prime with no smooth structure, BSGS/Pohlig-Hellman are not the path. - Applying index calculus to a generic elliptic curve. It's a finite-field-specific algorithm (it needs a notion of "smooth" factorization of field elements over small primes, which elliptic curve points don't have). An ECDLP with no smoothness/anomalous/singular structure is genuinely hard — don't burn time trying to port index calculus to it; look for a different weakness instead (Invalid Curve Attack — leaking an ECDH secret through a point nobody checked was on the curve, nonce reuse, a leaked bit). - Reducing mod `p-1` (or the full curve order) instead of the actual order of `g`. It looks harmless but wastes the whole smoothness check on the wrong number and can make Pohlig-Hellman miss factors that only show up in the true subgroup order — always compute g.multiplicative_order() (or the actual point order) before factoring. - Trusting Pohlig-Hellman alone when one residual prime factor is still large. It correctly recovers x modulo every smooth factor, but if a big prime remains un-peeled, the CRT recombination is incomplete without also solving that last piece (index calculus, rho, or accepting a partial/brute-forceable range). - Attacking the DLP head-on when `n` is a large prime with no special structure at all. If the group order is prime, or close to it, and shows no smoothness, no anomalous/singular curve property, and isn't small enough for BSGS, the challenge's intended weakness is almost certainly elsewhere — a reused/biased nonce, a leaked partial key, a protocol/oracle flaw — not a direct break of the discrete log itself (see Key-Exchange Methodology — triage any DH/ECDH challenge before reaching for heavy DLP machinery).

Related

Baby-Step Giant-Step — the generic meet-in-the-middle solver for a mid-sized discrete log Pohlig-Hellman — solving the discrete log when the group order is smooth Index Calculus — sub-exponential DLP attack for large prime fields with no smooth structure Chinese Remainder Theorem — recombining residues across coprime moduli Elliptic Curve Discrete Logarithm Problem — the curve order's factorization picks your attack Smart Attack — the anomalous-curve signal that turns ECDLP into polynomial time Key-Exchange Methodology — triage any DH/ECDH challenge before reaching for heavy DLP machinery Cryptanalysis Methodology — classify the family before you reach for an attack