The Log Was Never the Weak Part: How Discrete-Log Cryptography Actually Breaks

1. The 256-Bit Paradox#

Four cryptographic groups walk onto the internet. NIST P-256 and Curve25519 -- both 256 bits wide -- each advertise roughly $2^{128}$ security, and after two decades of public scrutiny neither has been broken ^[1]. A third 256-bit curve, differing from the first two only in a hidden arithmetic property, can be broken on a laptop in polynomial time ^[2]. And a 1024-bit finite-field group -- four times the bit length of the curves -- is a realistic target for a well-funded adversary ^[3]. The operation an attacker has to invert is the same discrete logarithm in all four groups.

The variable that decided their fates was never the logarithm. It was the group.

That sentence runs against the way most of us first meet the subject. We are taught that a one-way function is hard, that a bigger key makes it harder, and that "solving the discrete log" is a single monolithic feat an attacker either can or cannot perform. This article argues the opposite, and it argues it as a claim you should not yet believe: the discrete logarithm is essentially never the weak part. The weak part is always the group -- some extra structure it carries, or the wrong group quietly substituted for the right one.

Two settings recur throughout. The first is the multiplicative group of a prime field, written $\mathbb{F}_p^*$, the home of classic finite-field Diffie-Hellman, DSA, and ElGamal. The second is the group of points on an elliptic curve over a finite field, the home of ECDH, ECDSA, and EdDSA. The plan is a guided tour of every known way the discrete log "breaks." Each stop will turn out to exploit a structural property of a chosen group rather than compute a faster logarithm, and the tour ends at the one break that survives even a flawless group: Shor's quantum algorithm.

By the end you will be able to look at any of the ten attacks in the literature and name, in one phrase, the structural property of the group it needs -- and see that a well-chosen group simply does not have it. To understand why the group is the variable, we have to go back to the moment the discrete log became something worth attacking at all.

2. What the Discrete Log Actually Is, and Where It Lives#

In November 1976, Whitfield Diffie and Martin Hellman published "New Directions in Cryptography" and handed two strangers a way to agree on a shared secret over a wiretapped line without ever having met ^[4]. Their construction is simple enough to state in a sentence, and in stating it they turned an obscure number-theoretic puzzle into the thing standing between an eavesdropper and your traffic.

The instant the DLP became a security assumption, a very old question acquired stakes: how hard is it, actually? And the first answer was unsettling, because it showed that the difficulty had nothing to do with the size of the numbers involved.

timeline
title Fifty years of attacking the discrete logarithm
section The problem and its floor
1976 : Diffie-Hellman make the discrete log a security assumption
1978 : Pohlig-Hellman shatters smooth-order groups : Pollard rho sets the sqrt-time floor
section The escape to curves
1985 : Miller and Koblitz move the log onto elliptic curves
1993 : MOV pairing transfer : Gordon adapts the Number Field Sieve to prime fields
1994 : Shor reduces the discrete log to quantum period-finding
section Structure strikes back
1998 : Anomalous trace-one curves fall in polynomial time
2002 : Weil descent breaks special binary curves
section Records and frontiers
2015 : Logjam weaponizes shared-prime precomputation
2019 : A 795-bit prime-field record : quasi-polynomial small-characteristic descent proven

The first structural lesson: Pohlig-Hellman#

In January 1978, Stephen Pohlig and Martin Hellman proved something that should have set the tone for the entire field ^[6]. Suppose the order of the group -- the number of elements -- factors into small primes, $n = p_1^{e_1} p_2^{e_2} \cdots p_r^{e_r}$. Then the discrete log does not have to be solved in the big group at all. It can be solved separately in each prime-power piece, where the numbers are tiny, and the answers glued back together with the Chinese Remainder Theorem.

The total work is on the order of $\sum_i e_i(\log n + \sqrt{p_i})$ -- dominated by the largest prime factor, not by the size of $n$.

Read that again with the thesis in mind. A group can be astronomically large and still offer no security, if its order happens to be a product of small primes. A 4096-bit group whose order is smooth falls instantly.

Security was never a property of "the log" or of the key length. It was a property of the group's order -- specifically, whether that order contains a large prime factor. The first thing anyone proved about the discrete log moved the weakness off the logarithm and onto a structural feature of the chosen group. Everything that follows is a variation on that move.

The escape that defines the rest of the article#

By the mid-1980s, the multiplicative group $\mathbb{F}_p^*$ had a second problem beyond smooth orders: it admitted index calculus, a family of sub-exponential attacks we will meet in Section 6. The response, arriving independently from two directions, was not a better logarithm algorithm. It was a change of group.

In 1985, Victor Miller ^[7] and, independently, Neal Koblitz ^[8] proposed replacing $\mathbb{F}_p^*$ with the group of points on an elliptic curve over a finite field. Their motivation was explicit and structural: the multiplicative group hands index calculus something to grip, and a general elliptic curve does not, so the same security should be reachable with far smaller keys.

This is the thesis in its constructive form -- when a group is weak, do not sharpen the attack, choose a group with less structure -- and it introduces the lens we will look through for the rest of the article: the distinction between a generic group, whose elements are opaque handles you can only combine with the group operation, and a structured group, whose elements leak extra arithmetic an attacker can exploit.

Miller and Koblitz had escaped one kind of structure. The question their move raised -- and the one the next section answers -- is what an attacker can do against a group that has nothing wrong with it. If Pohlig-Hellman is defeated by a large prime order, how hard is the log then?

3. The Generic Floor: Why Square-Root Time Is the Best You Can Do#

Here is a number that has barely moved in fifty years. Against a well-chosen group, the best known generic attack on the discrete log runs in about $0.886\sqrt{\ell}$ steps, where $\ell$ is the largest prime factor of the group's order. Not only is that the best anyone has found -- there is a proof you cannot do fundamentally better generically. To see why that floor exists, and why it is a floor and not a ceiling waiting to be lowered, start with the simplest attack that hits it.

Baby-step giant-step: sorting your way to the log#

In 1971 Daniel Shanks described a deterministic method that trades memory for time ^[9]. To solve $h = g^x$ with $x$ below some bound $N$, precompute and store the "baby steps" $g^0, g^1, \ldots, g^{m-1}$ for $m \approx \sqrt{N}$, then take "giant steps" $h \cdot g^{-jm}$ for $j = 0, 1, 2, \ldots$ until one lands in the stored table. A match pins down $x = i + jm$. The running time is $O(\sqrt{N})$ and so is the memory -- and remarkably, this square-root cost is essentially the same one that still bounds the state of the art.

The memory is the problem. Storing $\sqrt{\ell}$ group elements is fine for a 40-bit group and impossible for a 256-bit one. The breakthrough was getting the same square-root time with almost no memory at all.

Pollard's rho: a random walk that traps itself#

John Pollard published this in 1978 ^[11]. Its beauty is the memory: using Floyd's or Brent's cycle-finding, you need to remember only a couple of points, so the cost is about $0.886\sqrt{\ell} = \sqrt{\pi/4}\,\sqrt{\ell}$ group operations at $O(1)$ space. The name comes from the shape the walk traces -- a tail that runs into a loop, like the Greek letter rho.

flowchart TD
A[Start at a known element, tracking exponents a and b] --> B[Apply the pseudo-random step f]
B --> C[Land on the next element of the walk]
C --> D{"Element seen before?"}
D -->|No, keep walking| B
D -->|Yes, collision| E[Two products in g and Q name the same element]
E --> F[The collision becomes a linear equation in the unknown x]
F --> G[Read off the discrete log x]

You can watch the birthday collision happen on a toy group. The subgroup below has prime order $\ell = 509$, so $\sqrt{\ell} \approx 23$; the walk finds its self-collision in a few dozen steps and reads off the secret exponent.

# Group: the order-509 subgroup of the integers mod 1019. Q = g^x; recover x.
p, l, g = 1019, 509, 4      # p = 2*l + 1 (safe prime); g has prime order l
x_secret = 137              # the exponent the attacker does not know
Q = pow(g, x_secret, p)

def step(X, a, b):
  # A three-way pseudo-random walk that also tracks X = g^a * Q^b (mod p).
  r = X % 3
  if r == 0:   return (X * Q) % p, a, (b + 1) % l
  elif r == 1: return (X * X) % p, (2 * a) % l, (2 * b) % l
  else:        return (X * g) % p, (a + 1) % l, b

seen = {}                   # a table only to make the collision visible
X, a, b = g, 1, 0           # start at X = g^1 * Q^0
for i in range(1, l + 5):
  if X in seen:
      a2, b2 = seen[X]
      den = (b - b2) % l
      x = ((a2 - a) * pow(den, -1, l)) % l   # solve the collision for x
      print("collision at step", i, " (sqrt(l) is about", round(l ** 0.5), ")")
      print("recovered x =", x, " true x =", x_secret, " match:", x == x_secret)
      break
  seen[X] = (a, b)
  X, a, b = step(X, a, b)

A production attacker drops the table and uses constant memory, restarting on the rare degenerate collision where the bookkeeping cancels. What matters is the exponent: the cost scales as the square root of the subgroup order, and nothing about the group's size changes that scaling.

Parallelism does not change the exponent#

In 1999, Paul van Oorschot and Michael Wiener turned rho into a production weapon ^[12]. Many machines walk independently and report only distinguished points -- points with a rare, easy-to-test property such as a run of leading zero bits. A collision between any two chains is caught by a central server, and the speedup is near-linear: $m$ machines finish in about $\sqrt{\ell}/m$ wall-clock time. Parallelism buys you a smaller constant and a division by your budget. It does not touch the square root.

The floor is a theorem, not a lack of imagination#

Why be sure no cleverer generic walk exists? Because in 1997 Victor Shoup proved a matching lower bound: any algorithm that uses only the group operation must make $\Omega(\sqrt{\ell})$ queries to solve the discrete log, where $\ell$ is the largest prime factor of the order ^[13]. Pollard's upper bound and Shoup's lower bound close on the same exponent.

On a group with no exploitable structure, the best attack anyone knows -- Pollard rho at about $0.886\sqrt{\ell}$ steps -- is provably the best attack anyone generically can know, because Shoup's $\Omega(\sqrt{\ell})$ lower bound meets it. The two bounds coincide at $\Theta(\sqrt{\ell})$. The hardness is not a property of "the logarithm." It is fixed entirely by one number: the largest prime factor of the group's order. The variable has moved from the operation to the group.

That is why "security level" is defined as the rho cost. A 256-bit curve is a $2^{128}$ target, not a $2^{256}$ one, because rho gets a square-root discount that no key-size increase can revoke.

State-of-the-art attacks on the elliptic-curve discrete log are still within a factor of two of Shanks's 1971 method. Half a century of cryptanalysis against a clean curve has bought a factor of two.

The records bear this out. The largest discrete log ever solved on a generic, randomly chosen prime-field elliptic curve is a 112-bit curve, secp112r1, cracked in 2009 by a parallel rho computation ^[14]. The only solves that have reached higher leaned on exploitable curve structure rather than a stronger generic attack, which is the thesis in miniature. Set that against the finite-field records we are about to meet, where the numbers run past 795 bits, and the gap tells the whole story: against a clean curve there is no better attack than the square-root walk, so records crawl.

This is the wall every attacker hits -- unless the group hands them a crack. So where are the cracks? They start with the curve you choose.

4. The Curve as the Weak Part, I: Special Curves That Transfer the Log Away#

The move to elliptic curves was supposed to strip out structure. But the first generation of curve choices smuggled it back in, and the way each weakness works is the quiet engine of this whole article. None of them computes a faster logarithm. Each one moves the logarithm out of the curve and into a different group where the log was never hard to begin with.

flowchart TD
A[ECDLP on the chosen curve E] --> B{"What structure did the curve leak?"}
B -->|Trace equals 1, so the point count equals p| C[Additive transfer, the SSSA map]
B -->|Small embedding degree k| D[Pairing transfer, MOV and Frey-Ruck]
C --> E[Log now lives in the additive group of F_p, which has no hardness]
D --> F[Log now lives in a finite field where index calculus finishes it]
E --> G[Recovered in polynomial time]
F --> H[Recovered in sub-exponential time]

Anomalous curves: a trapdoor hiding in the point count#

Every elliptic curve over a prime field $\mathbb{F}_p$ has a point count governed by a single integer. Hasse's theorem says $\#E(\mathbb{F}_p) = p + 1 - t$, where $t$ is the trace of Frobenius and $|t| \le 2\sqrt{p}$. That one number, $t$, decides whether the curve is world-class or worthless.

When the group order equals $p$, a map exists -- built from the $p$-adic (formal) logarithm and expressible through Fermat quotients -- that sends the elliptic-curve discrete log straight into $(\mathbb{F}_p, +)$, the additive group of the field. And addition has no discrete-log hardness at all: recovering $x$ from $x \cdot a$ in $(\mathbb{F}_p, +)$ is one modular division. The transfer runs in polynomial time.

This was worked out in 1998 and 1999 by Nigel Smart ^[2], and independently by Igor Semaev ^[15] and by Takakazu Satoh and Kiyomichi Araki ^[16]; the attack is often abbreviated SSSA after the four names.

There is a subtlety worth flagging so you can spot a common mis-citation: this 1998-99 break is the additive, formal-logarithm transfer. It is not Semaev's later 2004 work on summation polynomials ^[17], which is a different line of attack we will meet in Section 10. Trace one is a coincidence in the point count; summation polynomials are an index-calculus program. Conflating them is the classic error in retellings of this attack.

Low embedding degree: a bridge into a weaker field#

The second transfer needs a different structural flaw. Every prime-order subgroup of a curve has an embedding degree, and if it is small, a bridge opens into a finite field where the log is soft.

The bridge itself is a bilinear pairing.

Menezes, Okamoto, and Vanstone published the Weil-pairing reduction in 1993 ^[20]; Frey and Ruck gave the companion Tate-pairing version in 1994 ^[21]. The classic victims are supersingular curves, which have embedding degree $k \le 6$. Once transferred into $\mathbb{F}_{q^k}^*$ with small $k$, the log falls to the sub-exponential Number Field Sieve of Section 6.

The escape to a curve is undone by a curve that quietly kept a low-degree door into a field. The defense, again, is a property of the curve you choose: demand a large embedding degree, which the pairing textbook literature treats as a standard selection criterion ^[22].

Step back and notice what both attacks have in common with each other and with Pohlig-Hellman before them.

Trace one and small embedding degree are properties an attacker can only hope the designer chose badly. The next family of breaks is nastier, because they can be triggered by the attacker's own inputs, or by a field chosen one level up from the curve.

5. The Curve as the Weak Part, II: Twists, Shadow Groups, and Descent#

The cleanest structural weakness of all does not live in the curve you publish. It lives in the curve's twin.

Twist attacks: falling off the curve onto its shadow#

Fast elliptic-curve implementations often work with $x$-coordinates only -- the Montgomery ladder, used by X25519, never computes a $y$-coordinate at all. That is a real speed and safety win, but it introduces a subtlety: an $x$ value the attacker sends might not correspond to any point on $E$.

Here is the attack. If the twist $E'$ has a smooth order -- a product of small primes -- then a scalar multiplication the victim performs on that twist leaks the secret modulo each small prime, exactly the Pohlig-Hellman shattering from Section 2, now triggered by an attacker's chosen input rather than by the designer's bad luck. Collect enough small residues and the Chinese Remainder Theorem reassembles the key.

The weakness is real, and again it is a property of the group the designer chose: it is defeated by requiring the twist's order, not just the curve's, to be near-prime. Curve25519 was designed to be twist-secure from the start ^[24], and SafeCurves treats twist security as a first-class criterion ^[1].

Invalid-curve shadow groups: arithmetic that forgets its own curve#

The next mechanism is sharper still, and it exposes something almost philosophical about how curve arithmetic works.

Biehl, Meyer, and Muller analyzed this in 2000 ^[25], and SafeCurves states the load-bearing fact plainly: the standard formulas do not involve the constant coefficient $b$ ^[1]. What makes this a "shadow group" rather than a single weak curve is that the attacker gets to choose $c$, and so gets a whole family of weaker curves to hunt through for one with a smooth order.

Now, the honest boundary. The mechanism above is pure group arithmetic -- a genuine structural property of the short-Weierstrass addition law -- and that is what belongs here. What makes it fire in a real system is a missing check: the software accepted a point without verifying it was on the intended curve. That trigger is an implementation gap, not curve mathematics, and this article deliberately stops at the mathematics.

Weil descent: a weakness chosen one level up, in the field#

The last structural break in this pair does not need a bad curve so much as a badly chosen field. Some curves live over binary extension fields $\mathbb{F}_{2^n}$. When the extension degree $n$ is composite, a technique called Weil restriction can re-express the curve's group as points on a higher-genus curve over a smaller subfield -- and on that higher-genus object, index calculus applies and beats the generic square-root floor.

Gaudry, Hess, and Smart formalized this in 2002 ^[26], and the title of their paper is itself a summary of this whole section: "Constructive and destructive facets of Weil descent on elliptic curves." The precondition is structural and specific: a composite-degree binary extension field. The defense is equally specific: use prime fields, or at worst prime-degree extensions, so there is no subfield to descend into.

Every curve break in these two sections has needed a particular structural precondition -- trace one, small embedding degree, a smooth twist, $b$-independent arithmetic, a composite extension field. Not one has been a faster logarithm. Now cross the aisle to the group the whole field was fleeing in 1985. There, the structure is not an accident of a bad curve. It is built into the group itself.

6. The Finite-Field Side: When the Group Itself Has Structure#

An anomalous curve is a bad choice -- pick a different curve and the weakness is gone. The multiplicative group $\mathbb{F}_p^*$ is different. It is not a bad choice; it is inherently structured. Its elements are ordinary integers, and integers can be multiplied and factored. That single property -- the one thing an elliptic-curve group pointedly does not have -- is exactly what the fastest classical attack needs.

Index calculus: turning multiplication into linear algebra#

Notice what index calculus consumes: the ability to factor group elements into small pieces. In $\mathbb{F}_p^*$ that ability is free, because the elements are integers. On an elliptic curve there is no such thing as a "small" point, no factor base, no notion of a smooth point at all. The attack has nothing to grip. That absence is not a minor detail -- it is the entire reason elliptic-curve cryptography exists.

The Number Field Sieve, pointed at the logarithm#

The mature form of this idea is the Number Field Sieve. Built for factoring by Lenstra, Lenstra, Manasse, and Pollard in 1990 ^[27], it was adapted to the discrete log in a prime field by Daniel Gordon in 1993 ^[28].

Its pipeline has four stages: choose number fields tuned to $p$ (polynomial selection), sieve for smooth relations (relation collection), solve the resulting sparse linear system modulo the group order (linear algebra), and then peel off each individual target log (descent). The first three stages depend only on the prime $p$ -- a fact that looks academic here and becomes a weapon in the next section.

Gordon's 1993 algorithm put the finite-field discrete log in the sub-exponential $L_p[1/3]$ class, with heuristic constant $3^{2/3} \approx 2.08$ ^[28]; later refinements sharpened that constant to the modern $(64/9)^{1/3} \approx 1.923$. To feel what the difference between $\alpha = 1/2$ and $\alpha = 1/3$ does to real key sizes, run the estimator: the finite-field cost grows like a cube root of the bit length in the exponent, while the elliptic-curve cost grows linearly. That is why the two settings need such different key sizes for the same security.

import math

def nfs_bits(bits):
  # Leading-term model of the NFS-DL cost L_p[1/3, (64/9)^(1/3)] for a 'bits'-bit prime.
  lnp = bits * math.log(2)
  c = (64 / 9) ** (1 / 3)                  # about 1.923
  return c * lnp ** (1/3) * math.log(lnp) ** (2/3) / math.log(2)

def rho_bits(order_bits):
  return order_bits / 2                    # Pollard rho: half the bit length

print("Finite-field DH (cost grows like a cube root in the exponent):")
for b in [512, 1024, 2048, 3072]:
  print(f"  {b:>4}-bit prime  ~  2^{nfs_bits(b):5.1f}")
print("Elliptic curve (cost grows linearly):")
for m in [160, 224, 256]:
  print(f"  {m:>4}-bit curve   ~  2^{rho_bits(m):5.1f}")
# The leading term runs a little high; calibrated against real records, standard
# practice reads 1024-bit as roughly 80-bit and 3072-bit as roughly 128-bit security.

The scaling is the point. A clean 256-bit curve and a 3072-bit prime deliver comparable security -- the curve does it with an eighth of the key length -- precisely because the curve denies the sieve its factor base. This is the thesis at its sharpest: the same discrete logarithm, but a group whose structure leaks drops the attack from square-root time all the way to $L_p[1/3]$.

Same discrete log. On a generic curve, the largest ever solved is 112 bits and the records crawl. In a prime field, the record is 795 bits and climbing. The logarithm did not change -- the group did.

The records make the gap concrete. The current prime-field discrete-log record is 795 bits (240 decimal digits), set in 2019 by Boudot, Gaudry, Guillevic, Heninger, Thome, and Zimmermann, with the discrete-log computation costing roughly 3,100 core-years ^[29]; the previous record was 768 bits ^[30]. Against the 112-bit generic-curve ceiling of Section 3, the sieve's structural advantage is not subtle. The multiplicative group hands the attacker a factor base; the curve hands them nothing. The results corroborate the standard textbook accounting of index calculus and its consequences for finite-field sizing ^[10].

A sub-exponential attack still sounds expensive -- years of computation for a single prime. So why is a 1024-bit Diffie-Hellman group a practical target rather than a merely theoretical one? Because the expensive part only has to be done once.

7. Logjam: Precomputation as a Structural Property#

The most misunderstood word in forward secrecy is "fresh." A new ephemeral key on every connection feels like it should defeat any precomputed attack -- surely a one-time secret cannot be broken by work done in advance. Against a shared prime, that intuition is simply wrong, and seeing why is the sharpest lesson the finite-field side has to teach.

Recall the four stages of the Number Field Sieve. Three of them -- polynomial selection, relation collection, and the enormous linear-algebra solve -- depend only on the prime $p$. They produce the discrete logs of the entire factor base, and that output is reusable for every discrete log computed in that same prime field. Only the final descent step depends on the particular target. The Logjam researchers put it in one line on the project page: the first step of the number field sieve is dependent only on this prime ^[3].

flowchart TD
subgraph PC["Precomputation, depends only on the prime p"]
A[Polynomial selection] --> B[Relation collection by sieving]
B --> C[Linear algebra, logs of the whole factor base]
end
C --> D[Per-target descent, one quick step per connection]
D --> E[Discrete log of this specific ephemeral key]
F[Every connection that shares p reuses the same precomputation] -.-> D

So a fresh ephemeral does not help if the prime behind it is shared and undersized. The attacker pays the sieve cost once, for the prime, and then every "fresh" handshake using that prime falls in the cheap descent step. Freshness protects the key; it does nothing for a shared group.

The blast radius came from exactly that reuse. A handful of 1024-bit primes were hard-coded into standards and shipped in software everywhere. Adrian and colleagues measured the exposure ^[3]. The immediate Logjam downgrade, forcing connections to 512-bit export-grade Diffie-Hellman, initially left 8.4% of the Top 1 Million HTTPS domains vulnerable.

Looking forward, a single precomputation against one common 1024-bit prime would let a passive eavesdropper read roughly 18% of the Top 1 Million HTTPS domains; precomputing a second common 1024-bit prime would reach about 66% of VPNs and 26% of SSH servers. A nation-state budget for one very large computation buys passive decryption of a striking fraction of the internet, all because the primes were shared.

There is a further twist this article names only to hand off: a prime can be maliciously constructed so that a hidden special-number-field-sieve structure makes it far weaker than it looks, a trapdoor invisible to anyone who did not build it. That, along with the wire-level mechanics of how a downgrade is actually negotiated, is deployment and protocol territory -- the empirical sibling's ground, not this article's.

Logjam attacks a field whose prime was too small and, above all, shared. But there is a family of fields where the sieve does not merely amortize -- it changes complexity class entirely, from sub-exponential to almost polynomial. The only question is which fields, and the answer is, once again, a structural property someone chose.

8. Small Characteristic: The Quasi-Polynomial Frontier#

For one specific family of fields, the discrete log came close to collapsing -- and the story teaches the same lesson one more time, in its most dramatic form: the characteristic you choose is a structural gift to the attacker.

Finite fields come in two flavors that matter here. Prime fields $\mathbb{F}_p$ have large characteristic $p$. Extension fields like $\mathbb{F}_{2^n}$ and $\mathbb{F}_{3^n}$ have small, fixed characteristic (2 or 3) and a large extension degree $n$. For decades both were treated as roughly comparable homes for the discrete log. Then, in the span of a few years, the small-characteristic case fell apart.

In 2013, Antoine Joux broke the long-standing $L[1/3]$ barrier for small-characteristic fields with a new index-calculus algorithm of complexity $L[1/4 + o(1)]$, published at Selected Areas in Cryptography ^[31]. That was the crack in the dam. In 2014, Barbulescu, Gaudry, Joux, and Thome went much further, giving a heuristic quasi-polynomial algorithm -- cost $n^{O(\log n)}$ -- for the discrete log in finite fields of small characteristic ^[32]. Quasi-polynomial is not merely faster than sub-exponential; it is a different universe of growth, far below $L[1/3]$.

Then in 2019, Kleinjung and Wesolowski removed the heuristics, proving that the discrete log in a fixed-characteristic field can be solved in expected time $(pn)^{2\log_2(n) + O(1)}$ -- a genuine theorem, not a conjecture backed by experiments ^[33].

Why does small characteristic collapse when a prime field does not? The whole descent turns on one structural gift. In a field like $\mathbb{F}_{2^n}$ every element is a low-degree polynomial over a tiny base field, and the Frobenius map $x \mapsto x^p$ acts linearly on that representation, because $(a + b)^p = a^p + b^p$ in characteristic $p$. Those two facts hand the attacker a cheap, self-replenishing supply of low-degree relations: the algorithm presents the field through a low-degree identity linking an element to its Frobenius image, so a single relation spawns a whole orbit of them essentially for free.

The attack then descends on degree. It rewrites the logarithm of a degree-$d$ target as a combination of logarithms of strictly lower-degree elements, recurses ($d \to d/2 \to \cdots$), and bottoms out at degree-one elements whose logs are read off directly. Because each step roughly halves the degree while spawning only quasi-polynomially many sub-problems, the descent tree has depth about $\log d$ and terminates in $n^{O(\log n)}$ time -- that logarithmic recursion depth is exactly why the exponent is "quasi-," not fully, polynomial.

A prime field $\mathbb{F}_p^*$ offers none of this. Its elements are integers modulo $p$, with no subfield tower, no element degree to shrink, and no small-characteristic Frobenius to make relations cheap. The descent has nothing to grip, which is precisely why the Number Field Sieve at $L_p[1/3]$ stays the best attack there.

The practical consequence was immediate: this line of work retired small-characteristic pairing choices, including the supersingular binary curves once proposed for pairing-based cryptography, whose security rested on a small-characteristic field discrete log. The field that was supposed to be the hard part evaporated.

The calibration is almost comical in scale. The record discrete log in a fixed-characteristic field now stands at $\mathrm{GF}(2^{30750})$, computed in 2019 ^[34]. That field is roughly thirty-nine times larger in bit length than the 795-bit prime-field record from the same era. Same "discrete logarithm"; the characteristic of the chosen field decides whether the records sit near 800 bits or sail past 30,000.

Eight sections, eight breaks, and one relentless pattern: every classical break so far -- Pohlig-Hellman, the anomalous transfer, MOV and Frey-Ruck, twists, invalid-curve shadows, Weil descent, the Number Field Sieve, and now small-characteristic descent -- needs a specific structural property of the chosen group. But a pattern is only convincing if you can see all of it at once. Lay every attack on a single table, and the thesis stops being a claim you have to trust and becomes something you can read straight off a column.

9. A Map of Where the Weakness Lives#

One table, read down one column, is the whole argument. Here is every attack in this article, each with the structural property it requires, the easy group it reduces the log to, its cost, and the one question that matters -- does a well-chosen group have that property?

Read the "group property it needs" column from top to bottom. Every classical attack that beats square-root time names a specific structural precondition -- a smooth order, trace one, low embedding degree, a smooth twist, $b$-independent arithmetic, a composite extension field, a factor base, small characteristic. The only two rows needing no structure are Pollard rho, which is the square-root floor, and Shor, which leaves the classical world entirely. Not one classical row is a faster generic logarithm. That is the thesis, rendered as a table.

The same pattern shows up in what a working engineer actually chooses between. Line up the deployed groups and the story is not "big keys versus small keys" -- it is "which structural weakness is present."

The two 256-bit curves and the 3072-bit prime all deliver about 128-bit security -- the curves with an eighth of the key length -- because a clean curve denies the sieve its factor base. And the two finite-field rows differ not by size alone but by sharing: the 1024-bit row is a target because its prime is common and precomputed, not merely because it is 1024 bits.

The table has one uncomfortable empty space. Every row is a break that needs structure, and a clean group has none of those structures. But is there a proof that a structure-free group is actually safe -- or have we simply never found the crack? To answer honestly, we have to admit what the entire edifice rests on.

10. Theoretical Limits: Is the Log Itself Ever the Weak Part?#

Here is the admission the whole subject rests on, and it is more unsettling than most textbooks let on: nobody has proved the discrete log is hard. Not for $\mathbb{F}_p^*$, not for a clean elliptic curve, not for any group that carries real traffic. The security of a large fraction of the internet rests on a problem no one can prove is difficult.

The only proven wall is Shoup's $\Omega(\sqrt{\ell})$ lower bound from Section 3 ^[13] -- and its scope is precisely the catch. It holds in the generic-group model, where the algorithm may not read anything from the encoding of group elements. It is a statement about structure-blind algorithms, not about the discrete log as such.

This is exactly why index calculus is not a paradox. The Number Field Sieve beats Shoup's $\sqrt{\ell}$ floor for $\mathbb{F}_p^*$ not because the proof is wrong but because $\mathbb{F}_p^*$ is not a generic group: its elements are integers, the algorithm reads their factorizations, and the generic model's central assumption simply does not apply. Every faster attack in this article is another group that leaves the generic model through some door of its own. The matching bound of Section 3 is real, and it is real only inside a model that structured groups escape.

The sharpest open question sits one level down, and it is the one that keeps elliptic-curve cryptographers honest: does a sub-exponential, index-calculus-style algorithm exist for the ECDLP over a prime field? If it did, it would do to elliptic curves what the Number Field Sieve did to finite-field Diffie-Hellman -- collapse the square-root advantage that justifies 256-bit keys.

So, classically and as far as anyone knows, a clean group leaves the square-root floor standing. There is no known sub-exponential attack on a well-chosen prime-field curve, and the conjecture that none exists is exactly that -- a conjecture, the working hypothesis behind every ECC key-size recommendation.

If the log's classical hardness is unproven yet unbroken on a clean group, then the only known way to break such a group is not a cleverer algorithm in the same world. It is to change worlds -- to a machine that computes on a fundamentally different substrate.

11. The Third Road: Shor, and Why a Clean Group Leaves Only Quantum#

Strip a group of every exploitable structure and the classical attacker is back at Pollard's 1978 random walk, hitting the square-root wall with no crack to exploit. The one thing left that beats that wall does not compute a cleverer logarithm. It runs on a different machine.

In 1994, Peter Shor showed that a quantum computer could solve both integer factoring and the discrete log in polynomial time ^[36]. The discrete-log algorithm does not attack the group's structure the way index calculus does. It rewrites the problem into a shape a quantum computer is uniquely good at. Framed abstractly, Shor's discrete-log routine solves a hidden subgroup problem: the secret $x$ hides a subgroup of $\mathbb{Z}_\ell \times \mathbb{Z}_\ell$ generated by $(x, 1)$, and the quantum Fourier transform is the tool that exposes it ^[38]. The abelian hidden-subgroup problem is the common engine behind Shor's factoring and discrete-log algorithms alike.

flowchart TD
A[Target: Q equals x times P on a clean curve] --> B[Build a function periodic in the unknown x]
B --> C[Evaluate it over a superposition on the quantum register]
C --> D[Quantum Fourier transform makes the period observable]
D --> E[Measure: each shot yields a linear relation in x, mod l]
E --> F[Solve the linear congruences for the discrete log x, polynomial in log of the order]

The consequence is the one classical cryptanalysis can never deliver: the cost is polynomial in $\log \ell$, so key size is no defense. Doubling the curve size barely moves Shor's cost. And it needs none of the structural preconditions from the table in Section 9 -- no trace one, no small embedding degree, no smooth twist, no factor base. It breaks a correct key on a flawless group. Shor is the empty cell filled in: the only known attack that does not require the group to be badly chosen.

Crucially, the progress since 1994 has been algorithmic, not hardware. The first ECDLP-specific quantum circuit came from Proos and Zalka in 2003, who made a structural observation that still holds: elliptic curves are an easier quantum target than equal-security RSA ^[39].

The modern resource estimate, from Roetteler, Naehrig, Svore, and Lauter in 2017, is concrete: a 256-bit ECDLP needs about 2,330 logical qubits -- following their count of $9n + 2\lceil\log_2 n\rceil + 10$, which for $n = 256$ gives $2304 + 16 + 10 = 2330$ -- and on the order of $1.3 \times 10^{11}$ Toffoli gates, versus roughly 6,146 logical qubits for RSA-3072 ^[40]. The curve's small keys, its great classical advantage, make it the cheaper thing to break once a quantum computer exists.

Two honest boundaries close this section. First, no cryptographically-relevant quantum computer exists today, and this article asserts no timeline for when, or whether, one will. The resource estimates set a migration clock, not a countdown. Second, the genuine successor to discrete-log cryptography is post-quantum cryptography -- schemes built on entirely different hard problems such as lattices, error-correcting codes, and hash functions. That is a separate research program, out of scope here, and its independence is the point: it is not a faster discrete log but a different foundation.

So the mathematics is settled enough to act on. Choose a group with no weak part, and the classical attacker is stranded at the square-root floor; the only remaining break is one you cannot out-size, and the response to it is migration, not a bigger key. That leaves one practical question: how do you actually choose a group with no weak part? Every criterion is a scar from an attack in this article.

12. Choosing a Group With No Weak Part#

Every line on a curve-selection checklist is a scar from a specific attack in this article. Read the checklist not as arbitrary hygiene but as a map of defeated enemies -- each criterion exists because someone, somewhere, lost a key to the attack it blocks.

Two of these checks are easy enough to run on a toy example, which makes the abstract concrete: a curve is anomalous exactly when its point count equals the field prime, and it has a dangerous embedding degree exactly when the subgroup order divides $p^k - 1$ for some small $k$.

def embedding_degree(l, p, bound=200):
  # least k with l dividing p^k - 1; small k means a MOV / Frey-Ruck door
  r = p % l
  for k in range(1, bound + 1):
      if r == 1:
          return k
      r = (r * p) % l
  return None  # beyond the search bound: safely large

def score(p, n, l):
  flags = []
  if n == p:
      flags.append("ANOMALOUS: #E equals p, trace one -> polynomial-time SSSA transfer")
  if n % l == 0:
      k = embedding_degree(l, p)
      if k is not None and k <= 6:
          flags.append("LOW EMBEDDING DEGREE k=" + str(k) + " -> MOV / Frey-Ruck transfer")
      if n // l > 8:
          flags.append("LARGE COFACTOR " + str(n // l) + " -> small-subgroup leakage")
  else:
      flags.append("subgroup order does not divide the point count (bad parameters)")
  return flags or ["no structural red flag on these two checks"]

print("anomalous toy (p = n = 23):", score(23, 23, 23))
print("low-k toy (p=23, points=24, order=3):", score(23, 24, 3))
print("clean toy (p=101, points=order=83):", score(101, 83, 83))

The decision, in one flow#

flowchart TD
A{"What are you building?"} -->|New system, free choice| B[X25519 for key exchange, Ed25519 for signatures]
A -->|FIPS-constrained| C[NIST P-256]
A -->|Finite-field DH is forced| D[A standard RFC 7919 group of at least 2048 bits, never a shared 1024-bit prime]
B --> E[Verify large prime order, small cofactor, trace not one, large embedding degree, twist-secure, rigid]
C --> E
D --> F[Plan a post-quantum or hybrid migration for the Shor horizon]
E --> F

For a new system with a free hand, use X25519 for key exchange and Ed25519 for signatures ^{[43] [44]}: they are twist-secure and rigid by construction, and they close every classical door in the table above. Where a standard mandates the NIST curves, P-256 is a sound choice with the same generic-floor security ^[35]. If finite-field Diffie-Hellman is genuinely unavoidable, use a standard RFC 7919 group of at least 2048 bits -- its shared named groups are safe at this size because the sieve precomputation is infeasible -- or a dedicated unique prime; never a shared or legacy 1024-bit prime, whose danger was the entire lesson of Logjam ^[45].

And across the board, avoid the families this article condemned: anomalous curves, low-embedding-degree curves, small-characteristic fields, and the binary and Koblitz curves that NIST now deprecates and FIPS 186-5 removes ^[35].

One caveat belongs to the sibling article, not this one: choosing a strong group is necessary but not sufficient. A flawless curve still fails if the software forgets to validate an input point, reuses a nonce, or leaks timing -- the implementation failures catalogued in "How Elliptic Curves and Diffie-Hellman Break in Real Life." This article guarantees only that the mathematics of a well-chosen group offers no purchase. The code still has to hold up its end.

That covers what to do. The questions careful engineers keep asking -- and the misconceptions that trip up even good ones -- deserve direct answers.

13. Frequently Asked Questions#

The Log Was Never the Weak Part#

Return to the four groups from the opening. NIST P-256 and Curve25519 stand at about $2^{128}$ because they have large prime order, trace not one, large embedding degree, twist-security, and rigid parameters -- every structural door bolted shut, leaving only the square-root floor.

The third 256-bit curve dies in polynomial time for one reason: its trace is one, so its log transfers into simple addition. And the 1024-bit finite-field group is a nation-state target because its group is inherently factorable and its prime was shared and precomputed. Four groups, the same discrete logarithm, three different fates -- and in every case the deciding variable was the group.

Same discrete log, radically different fates. The variable was never the logarithm. It was the group.

That is the pattern under all ten attacks. Pohlig-Hellman needs a smooth order. The anomalous transfer needs trace one. MOV and Frey-Ruck need a small embedding degree. Twist attacks need a smooth twist. Invalid-curve shadows need $b$-independent arithmetic. Weil descent needs a composite extension field. The Number Field Sieve needs a factor base. Logjam needs a shared prime. Small-characteristic descent needs a small characteristic. Every classical break is a receipt for a structural property of a chosen group, and never once a faster generic logarithm.

Strip a group of every exploitable structure -- give it a large prime order, a small cofactor, trace not one, a large embedding degree, twist-security, rigidity, a prime field, no small characteristic, and a unique well-sized prime -- and the classical attacker is thrown all the way back to Pollard's 1978 random walk. The only thing left that beats it does not compute a cleverer logarithm; it changes the machine. The logarithm was never the weak part. The group always was.

Which is why the rational response has two halves. Choose a clean group -- the checklist in Section 12 is really a list of defeated attacks -- and begin preparing for the one break you cannot out-size, by planning the migration to post-quantum primitives before a quantum computer forces the issue.

For the failures that live in code rather than mathematics -- unvalidated points, repeated nonces, timing leaks, negotiated downgrades -- turn to the empirical sibling, "How Elliptic Curves and Diffie-Hellman Break in Real Life." The mathematics here gives you a group with no weak part. The engineering there decides whether your system keeps it that way.