Discrete Logarithm Problem, in depth: why the group decides the cost, index calculus worked end to end, and parameters that stay hard

The problem, stated precisely

Fix a finite cyclic group G of order n with generator g. Every element h of G equals g^x for exactly one x in [0, n); the DLP asks for that x. The forward direction is cheap: square-and-multiply computes g^x in about 2 log2(x) group operations (see modular exponentiation). The question is whether the reverse direction can be anywhere near as cheap.

Protocols usually lean on two weaker relatives. The computational Diffie-Hellman problem (CDH) gives you g^a and g^b and asks for g^ab. The decisional problem (DDH) asks you merely to distinguish g^ab from a random element. Solving DLP solves CDH, and solving CDH solves DDH, so DDH is the strongest assumption and the easiest to lose.

A concrete example of losing it: in the full multiplicative group mod a prime p, the Legendre symbol of g^x reveals whether x is even. Since g^ab is a square exactly when a or b is even, an attacker can check that consistency and tell a real shared value from a random one. That is why careful protocols work in a subgroup of large prime order q rather than in the whole of Z_p*.

Why the group decides the difficulty

Take the additive group of integers mod n. There, "exponentiation" is multiplication, h = x * g mod n, and the extended Euclidean algorithm recovers x instantly. The group is cyclic and the problem is formally a DLP, but the representation hands the attacker everything. Hardness is a property of how the group is represented.

At the other extreme sits the generic group model: the attacker may only multiply, invert and compare elements, without looking at their encodings. Shoup proved in 1997 that any such algorithm needs on the order of sqrt(q) operations, where q is the largest prime factor of n. Baby-step giant-step and Pollard rho match that bound, and Pohlig-Hellman shows why only the largest prime factor counts: it solves the problem separately in each prime-power subgroup and stitches the answers together with the Chinese remainder theorem.

Real groups sit in between, and their extra structure is what matters:

Index calculus: logarithms of small primes

Index calculus exploits something prime fields have and generic groups do not: elements are integers, and integers factor. The logarithm is a homomorphism, log(a*b) = log a + log b (mod p-1), so if you know the logarithms of a few small primes, you know the logarithm of every number that factors entirely over them. The algorithm has three phases:

1. Relation collection. Choose a factor base B of small primes. Pick random k, compute g^k mod p and try to factor it over B. Each success gives a linear equation k = sum(e_i * log q_i) (mod p-1).
2. Linear algebra. With a few more relations than unknowns, solve the system modulo p-1. Since p-1 is composite, solve modulo each of its prime factors and recombine with the CRT. Now every factor-base prime has a known logarithm.
3. Descent. For the target h, pick random s until h * g^s mod p is smooth over B. Then log h = sum(e_i * log q_i) - s (mod p-1).

The expensive phases 1 and 2 depend only on p and g, not on h. That fact is the whole story of the Logjam attack, covered below.

Worked example modulo 1019

Take p = 1019, so p - 1 = 1018 = 2 * 509 with 509 prime. The element 2 has order 1018, so g = 2 generates the group. Use the factor base {2, 3, 5, 7, 11, 13}. In our run, 23.8% of random powers of 2 factored over this base, so collecting 16 relations takes about 70 tries.

Some relations are easy to read. 2^10 = 1024 = 5 (mod 1019) gives log 5 = 10 directly. 2^27 = 143 = 11 * 13 gives log 11 + log 13 = 27. After the elimination, the solved logarithms are log 2 = 1, log 3 = 958, log 5 = 10, log 7 = 363, log 11 = 756 and log 13 = 289. Check one: 756 + 289 = 1045, which is 27 modulo 1018, as the relation demands.

Now find log_2 777. Trying shifts s = 1, 2, ..., the first smooth value is at s = 11: 777 * 2^11 mod 1019 = 637 = 7^2 * 13. So log 777 = 2*363 + 289 - 11 = 1004, and indeed 2^1004 mod 1019 = 777. Running the code below on every target from 1 to 1018 returned the correct logarithm in all 1,018 cases.

A complete implementation

import random

def factor_over(n, base):
    """Exponent vector of n over the factor base, or None if n is not smooth."""
    exps = []
    for q in base:
        e = 0
        while n % q == 0:
            n //= q
            e += 1
        exps.append(e)
    return exps if n == 1 else None

def solve_mod(rows, rhs, ell):
    """Gauss-Jordan elimination mod a prime ell; None means rank deficient."""
    m = [r[:] + [b] for r, b in zip(rows, rhs)]
    ncol, piv_row, where = len(rows[0]), 0, {}
    for col in range(ncol):
        sel = next((i for i in range(piv_row, len(m)) if m[i][col] % ell), None)
        if sel is None:
            return None
        m[piv_row], m[sel] = m[sel], m[piv_row]
        inv = pow(m[piv_row][col], -1, ell)
        m[piv_row] = [x * inv % ell for x in m[piv_row]]
        for i in range(len(m)):
            if i != piv_row and m[i][col] % ell:
                f = m[i][col]
                m[i] = [(a - f * b) % ell for a, b in zip(m[i], m[piv_row])]
        where[col] = piv_row
        piv_row += 1
    return [m[where[c]][-1] for c in range(ncol)]

def index_calculus(g, h, p, base, ells, extra=10, seed=1):
    """log_g h mod p, where p - 1 is the product of the distinct primes in ells."""
    rng = random.Random(seed)
    rows, rhs = [], []
    while True:
        while len(rows) < len(base) + extra:        # phase 1: relations
            k = rng.randrange(1, p - 1)
            e = factor_over(pow(g, k, p), base)
            if e:
                rows.append(e); rhs.append(k)
        parts = [solve_mod(rows, rhs, l) for l in ells]   # phase 2
        if all(x is not None for x in parts):
            break
        extra += 5                                  # need more relations
    logs = []
    for i in range(len(base)):                      # CRT per factor-base prime
        x, mod = 0, 1
        for l, sol in zip(ells, parts):
            x += mod * ((sol[i] - x) * pow(mod, -1, l) % l)
            mod *= l
        logs.append(x)
    while True:                                     # phase 3: descent
        s = rng.randrange(1, p - 1)
        e = factor_over(h * pow(g, s, p) % p, base)
        if e:
            return (sum(a * b for a, b in zip(e, logs)) - s) % (p - 1)

x = index_calculus(2, 777, 1019, [2, 3, 5, 7, 11, 13], ells=[2, 509])
assert pow(2, x, 1019) == 777                       # x == 1004

Two simplifications keep this short. It assumes p-1 is squarefree, so each modulus in ells is a prime and elimination happens over a field; a prime-power factor needs Hensel lifting or Smith normal form instead. And it uses dense elimination, which costs cubic time in the factor-base size. Real implementations use sparse structured Gaussian elimination followed by block Lanczos or block Wiedemann, because the relation matrix has only a handful of nonzeros per row.

How it scales, and why curves resist it

The probability that a random number below p is smooth over primes up to B is roughly u^-u with u = ln p / ln B. A large B makes relations common but requires more of them; a small B makes them rare. Balancing the two gives the basic algorithm a running time of the form L_p[1/2], which is subexponential: slower than any polynomial, far faster than the sqrt(p) of rho. The number field sieve replaces "random powers of g" with pairs of smaller numbers in two number fields, improving the exponent to L_p[1/3].

Two consequences follow. First, field sizes must grow much faster than security levels. Second, because phases 1 and 2 depend only on p, one heavy precomputation breaks every key that shares the prime. The Logjam researchers (2015) spent about a week precomputing for a 512-bit export-grade group, then computed individual logs in that group in about a minute; they found most vulnerable servers sharing a single such prime. In December 2019 a team using CADO-NFS solved a DLP in a 795-bit safe prime field (DLP-240), reporting about 2,400 core-years of sieving and 700 core-years of linear algebra.

Elliptic curves resist all of this because a curve point has no notion of being "smooth": there is no known way to lift points to a ring where they factor into small pieces. For standard prime-field curves the best known attack is still Pollard rho, so the security level is about half the bit length of the group order.

Choosing parameters: guidance and trade-offs

NIST SP 800-57 lists comparable strengths, which make the gap concrete:

In practice: prefer X25519 or P-256 for key agreement and Ed25519 or ECDSA P-256 for signatures. If you must use finite-field Diffie-Hellman, use the named safe-prime groups from RFC 7919 at 2048 bits or more (3072 for long-lived secrets), never a home-made prime and never anything below 2048 bits. The Diffie-Hellman attack article shows what goes wrong when peers skip validation, and the elliptic curve cryptography article covers curve arithmetic and choice.

Then there is the quantum horizon. Shor's algorithm solves the DLP in polynomial time in every one of these groups, and curve keys are expected to fall with fewer logical qubits than RSA moduli of similar classical strength, because the groups are so much smaller. Recorded traffic can be decrypted later, so key exchange is migrating first: ML-KEM was standardised as FIPS 203 in 2024, and hybrid groups such as X25519MLKEM768 combine it with X25519 so a break of either alone is not enough.

Failure modes

• Small-subgroup confinement. If p-1 has small factors and a peer does not check that a received element lies in the order-q subgroup, an attacker sends elements of small order and learns the secret exponent modulo each small factor, then combines the pieces with the CRT. Fix: check h^q == 1 or use safe primes and reject 0, 1 and p-1.
• Invalid-curve points. The elliptic analogue: a point not on the curve can lie on a weaker curve that shares the addition formulas. Validate points or use X25519, which avoids invalid-curve attacks by design but still needs an all-zero output check.
• Short exponents. If x is known to lie in an interval of width w, Pollard's kangaroo method finds it in about sqrt(w) steps regardless of the group size. A 160-bit exponent in a 3072-bit group gives at most 80-bit security.
• Nonce reuse in DSA and ECDSA. Two signatures with the same k give k = (z1 - z2) / (s1 - s2) and then the private key, with no logarithm needed. Use deterministic nonces (RFC 6979) or a vetted library.
• Shared parameters. A fixed widely used 1024-bit prime invites the Logjam precomputation. Move to 2048-bit standard groups or, better, to curves.
• Timing leaks. Variable-time exponentiation can leak exponent bits that shrink the search interval. Use constant-time ladders.

What to do next

1. Run the index calculus code above for p = 1019, then try a 30-bit safe prime and watch how relation collection and elimination time change as you vary B.
2. Implement Pohlig-Hellman for a p whose p-1 is smooth and see how quickly a 64-bit instance falls; this is why group order matters more than modulus size.
3. Audit your code base for finite-field Diffie-Hellman below 2048 bits, custom primes and missing subgroup checks.
4. Confirm every ECDSA signer uses RFC 6979 nonces or a library that does.
5. Inventory long-lived confidential traffic and plan hybrid post-quantum key exchange for it.
6. Read the companion primitive roots article for the generic algorithms in detail.