up:: Classical Cryptography MOC

discrete logarithm problem

The discrete logarithm problem is the mathematical hardness assumption that a large share of public-key cryptography rests on. Given a starting number g and the result of raising it to a secret power, g^x mod p, the problem is to recover the exponent x. Computing the forward direction is fast, and reversing it is believed to be so slow on a classical computer that the secret stays safe. That one-way gap is what protects Diffie-Hellman key exchange and every elliptic-curve scheme, so when Shor’s algorithm solves the discrete logarithm efficiently on a quantum computer, all of that cryptography breaks at once.

The short version:

• The problem, in one line. Given g and g^x mod p, find x. Easy forward, believed hard to reverse classically, and that asymmetry is the whole security.
• It comes in two flavors. The finite-field version sits behind Diffie-Hellman and DSA. The elliptic-curve version (ECDLP) sits behind ECDH, ECDSA, and Ed25519.
• A huge share of public-key crypto depends on it. Nearly every key exchange and elliptic-curve signature in modern systems inherits its security from the discrete logarithm.
• Shor’s algorithm solves it in polynomial time. On a quantum computer, both flavors fall, which is why every discrete-log-based algorithm gets replaced rather than resized.
• It is one of two Shor-vulnerable assumptions. The other is integer factorization, the problem behind RSA. Shor’s algorithm defeats both, which is why RSA and discrete-log crypto all fall together.

Picture a clock face with a prime number of hour marks. Starting at one mark and stepping forward a fixed number of positions is quick, and if I tell you the step size, you can land on the answer in a moment. Now flip it around. I show you only where the hand ended up, and I ask how many steps it took to get there. On a small clock you could just count. On a clock with hundreds of digits’ worth of marks, the hand can wrap around so many times that working backward from the final position to the number of steps becomes hopeless for a classical computer. The forward step is the easy direction anyone can take, and the hidden step count is the secret. Recovering that step count is the discrete logarithm problem.

What is the discrete logarithm problem?

The discrete logarithm problem is the task of finding the exponent in a modular exponentiation when you know the base and the result. Formally, in a cyclic group with a generator g and an element h, it asks you to find the integer x such that g^x = h within that group. The word “discrete” separates it from the ordinary logarithm you learned in school, which works over the continuous real numbers. Here the arithmetic wraps around inside a finite mathematical group, so the usual smooth, approximate methods for taking a logarithm give you nothing.

Source: NIST SP 800-56A Rev. 3, “Recommendation for Pair-Wise Key-Establishment Using Discrete Logarithm Cryptography,” 2018, NIST.

The security of a discrete-log system comes entirely from choosing a group where the forward operation is cheap and the reverse is intractable at the sizes in use. Multiplying the group element by itself many times to compute g^x takes a fraction of a second. Going the other way, staring at h and trying to recover x, has no known efficient classical shortcut when the group is large and well chosen. That gap between easy forward and hard backward is the definition of a one-way function, and the discrete logarithm is one of the two one-way functions that classical public-key cryptography is built on.

How does the discrete logarithm problem work?

The problem lives inside a finite cyclic group, and the mechanism is easiest to follow through the finite-field setting first. Take a large prime p and a generator g. Raising g to successive powers modulo p cycles through the group’s elements in an order that looks scrambled and unpredictable, even though it is completely deterministic. To use it in cryptography, one party picks a secret exponent x, publishes g^x mod p, and keeps x private. Anyone can verify or combine the public value, and nobody without x can efficiently work it out.

The reason reversal is hard is that the exponentiation destroys the orderly structure a solver would need. The published value g^x mod p gives no clue how many times the base was multiplied to reach it, because the modular wrap-around erases the “size” information you would use to home in on the answer. The best known classical algorithms for the finite-field version, the index-calculus family, run in subexponential time, which is why the moduli have to be large. Modern standards require finite-field parameters of at least 2048 bits, and NIST maps a 3072-bit modulus to 128 bits of classical security strength.

Source: NIST SP 800-57 Part 1 Rev. 5, “Recommendation for Key Management,” 2020, Table 2, NIST.

The same shape of problem, moved into a different group, gives you the elliptic-curve version, and that shift is what lets elliptic-curve cryptography use far smaller keys for the same strength.

What are the two flavors of the discrete logarithm problem?

There are two group settings where the discrete logarithm underpins real cryptography, and knowing which one a given algorithm uses tells you its key sizes and its exact dependencies.

1. Finite-field DLP. The group is the integers modulo a large prime, and the secret is an exponent. This is the original setting behind classical Diffie-Hellman key exchange and the older DSA signature scheme. Its parameters are large because the index-calculus attacks work here, so a secure modulus runs 2048 bits or more.
2. Elliptic-curve DLP (ECDLP). The group is the set of points on an elliptic curve, and “raising to a power” becomes repeated point addition. This is the setting behind ECDH, ECDSA, and Ed25519. The index-calculus attacks that weaken the finite-field version do not apply to well-chosen curves, so much smaller parameters reach the same classical strength. NIST maps a 256-bit curve to roughly the 128-bit security of a 3072-bit finite-field modulus, which is why the industry moved to elliptic curves for the size and speed savings.

Source: NIST FIPS 186-5, “Digital Signature Standard (DSS),” 2023, NIST; NIST SP 800-57 Part 1 Rev. 5, Table 2, NIST.

The important thing for the quantum question is that both flavors are the same underlying problem wearing different clothes. A single quantum algorithm handles both, so the smaller, more efficient elliptic-curve version is not the safer choice against a quantum computer. It actually falls to a smaller quantum machine than a finite-field system of comparable classical strength.

Why does so much public-key cryptography rest on it?

Because the discrete logarithm solves the problem that made secure communication over an open line possible in the first place: how two strangers who have never met can agree on a shared secret while an eavesdropper watches every message. Diffie-Hellman key exchange, published in 1976, was the first practical answer, and it works precisely because each side can publish g^x without revealing x. From that foundation grew an entire family of algorithms, and the discrete logarithm became one of the two hard problems that essentially all deployed public-key cryptography leans on.

Here is the concrete footprint. Any algorithm in the following list inherits its security from the discrete logarithm, which means a break of the problem is a simultaneous break of all of them:

Algorithm	Job	Flavor of DLP	Quantum verdict	Replace with
Diffie-Hellman / DHE	Key exchange	Finite-field	Broken by Shor’s	ML-KEM
ECDH / ECDHE / X25519	Key exchange	Elliptic-curve	Broken by Shor’s	ML-KEM
ECDSA	Signatures	Elliptic-curve	Broken by Shor’s	ML-DSA / SLH-DSA
Ed25519 / EdDSA	Signatures	Elliptic-curve	Broken by Shor’s	ML-DSA / SLH-DSA
DSA	Signatures	Finite-field	Broken by Shor’s	ML-DSA / SLH-DSA
ElGamal	Encryption	Finite-field	Broken by Shor’s	ML-KEM

These algorithms do both of public-key cryptography’s core jobs. They establish the keys that protect confidential traffic in TLS, IPsec, and SSH, and they produce the digital signatures that anchor trust. A single mathematical break takes down both jobs across every protocol that uses them, which is why the discrete logarithm sits at the center of the migration.

How does the quantum transition affect the discrete logarithm problem?

A quantum computer running Shor’s algorithm solves the discrete logarithm problem in polynomial time, which turns a problem that was intractable into one that is merely a computation. Peter Shor’s 1994 result, detailed in his 1997 paper, gave efficient quantum algorithms for both integer factorization and the discrete logarithm, and it covers both the finite-field and the elliptic-curve flavors. Once a cryptographically relevant quantum computer can run Shor’s at real parameter sizes, every discrete-log-based algorithm loses its security completely.

Source: P. W. Shor, “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer,” SIAM Journal on Computing, 1997, SIAM.

The critical consequence is that bigger keys do not save these systems. Against classical attackers, you buy security by enlarging the group, moving from 2048-bit to 3072-bit finite fields or to larger curves. Against Shor’s algorithm, the quantum cost grows only polynomially with the size of the problem, so a larger key adds qubits and runtime to the eventual attack without putting it out of reach. That is why NIST’s transition guidance treats discrete-log algorithms as things to replace on a schedule rather than parameters to keep tuning upward.

Source: NIST IR 8547 (initial public draft), “Transition to Post-Quantum Cryptography Standards,” 2024, NIST.

One clarification keeps this accurate. The threat here is Shor’s algorithm rather than Grover’s. Grover’s algorithm gives only a quadratic speedup on brute-force search, which weakens symmetric ciphers like AES while leaving the discrete logarithm untouched. Shor’s is what breaks it, and it breaks it completely.

Source: L. K. Grover, “A Fast Quantum Mechanical Algorithm for Database Search,” 1996, arXiv.

How does the discrete logarithm problem relate to integer factorization?

The discrete logarithm and integer factorization are the two hard problems that all widely deployed classical public-key cryptography rests on, and they are the two problems Shor’s algorithm was built to defeat. Factoring is the problem behind RSA: multiplying two large primes is easy, and pulling the product back apart is believed hard. The discrete logarithm is the problem behind Diffie-Hellman and the elliptic-curve family. They are different math, but they share a deep structure, and Shor’s algorithm exploits that shared structure to break both.

Property	Integer factorization	Discrete logarithm problem
The hard task	Recover the primes p and q from n = p × q	Recover the exponent x from g^x mod p
Algorithms that rely on it	RSA	DH, ECDH, ECDSA, Ed25519, DSA, ElGamal
Best classical attack	Subexponential (number field sieve)	Subexponential for finite fields, exponential for elliptic curves
Quantum attack	Shor’s algorithm, polynomial time	Shor’s algorithm, polynomial time
Fix bigger keys?	No, Shor’s cost grows polynomially	No, Shor’s cost grows polynomially
Post-quantum replacement	ML-KEM and ML-DSA	ML-KEM and ML-DSA

The practical upshot of the two problems collapsing together is that there is no classical safe harbor. A team cannot flee RSA to elliptic curves and call itself quantum-safe, because both hard problems dissolve under the same algorithm. That shared fate is why the answer is a new mathematical foundation entirely, the lattice and hash-based problems that the post-quantum standards are built on, rather than a move from one classical assumption to the other.

What replaces discrete-log cryptography?

The replacements are already standardized, and which one you use depends on the job. NIST finalized the first post-quantum standards on August 13, 2024, and they rest on mathematics that neither Shor’s algorithm nor any other known quantum attack solves efficiently.

Source: NIST, “NIST Releases First 3 Finalized Post-Quantum Encryption Standards,” August 13, 2024, NIST.

1. For key exchange, use ML-KEM. Wherever Diffie-Hellman or ECDH agreed on a shared secret, ML-KEM, a lattice-based key-encapsulation mechanism, is the direct successor. Its security does not depend on the discrete logarithm, so Shor’s algorithm has no purchase on it.
2. For signatures, use ML-DSA, with SLH-DSA as the conservative backup. Wherever ECDSA or Ed25519 signed data, ML-DSA is the general-purpose replacement, and the hash-based SLH-DSA is the option for the most conservative, long-lived trust anchors.

During the changeover most systems run hybrid key exchange, combining a classical algorithm like ECDH with ML-KEM so the result holds if either component survives. Designing so the algorithm can be swapped without rebuilding the surrounding systems is the point of crypto-agility, and finding every place a discrete-log algorithm hides is the point of a cryptographic inventory. The confidentiality half of the exposure is urgent today because of harvest now, decrypt later: traffic whose keys were agreed with Diffie-Hellman or ECDH can be recorded now and decrypted once the quantum computer arrives.

Common misconceptions

• “Elliptic-curve crypto is safer against quantum than finite-field Diffie-Hellman.” Both rest on the discrete logarithm and both fall to Shor’s algorithm. Elliptic curves actually break with a smaller quantum computer than a finite-field system of equivalent classical strength, so they are not the more quantum-resistant choice.
• “We can just use bigger keys or bigger curves.” Larger parameters defend against classical attacks, not against Shor’s algorithm, whose cost grows only polynomially with size. NIST is deprecating discrete-log algorithms at every parameter size.
• “The discrete logarithm and factoring are unrelated problems, so breaking one doesn’t threaten the other.” They are different math, but Shor’s algorithm solves both, so RSA and discrete-log cryptography share the same quantum deadline and fall together.
• “Grover’s algorithm is what breaks Diffie-Hellman.” Grover’s gives only a quadratic speedup and affects symmetric ciphers. The discrete logarithm is broken by Shor’s algorithm, completely, not by Grover’s.
• “Only key exchange is at risk, since that’s where Diffie-Hellman lives.” The discrete logarithm also underpins ECDSA, Ed25519, and DSA signatures, so both confidentiality and trust are exposed when it breaks.
• “There’s no working quantum computer, so discrete-log crypto is fine for now.” For anything meant to stay confidential for years, harvest-now-decrypt-later means keys agreed with discrete-log algorithms today are already exposed to a future quantum computer.

Questions people ask

What is a discrete logarithm in simple terms? It is the exponent you would need to recover in the equation g^x mod p when you can see g and the result but not x. Computing the forward direction is fast, and finding x by working backward is believed to be intractable classically for large, well-chosen groups, and that difficulty is what secures Diffie-Hellman and elliptic-curve cryptography.

What’s the difference between finite-field DLP and ECDLP? Both are the same problem in different mathematical groups. Finite-field DLP works with integers modulo a large prime and underpins classical Diffie-Hellman and DSA, needing 2048-bit or larger parameters. ECDLP works with points on an elliptic curve and underpins ECDH, ECDSA, and Ed25519, reaching the same classical strength with much smaller keys, roughly a 256-bit curve for 128-bit security.

Which algorithms break if the discrete logarithm is solved? All of Diffie-Hellman, ECDH, ECDSA, Ed25519, DSA, and ElGamal break simultaneously, because each inherits its security directly from the discrete logarithm. That covers most key exchange and elliptic-curve signatures in modern systems, which is why the problem is central to the migration.

Is the discrete logarithm harder than factoring? For classical attackers the two are comparable in difficulty at matched security levels, and NIST sizes them together (a 3072-bit RSA modulus and a 3072-bit finite-field group both sit at 128-bit security). For a quantum attacker they are equally doomed, since Shor’s algorithm solves both in polynomial time.

Does making the key bigger protect a discrete-log system from quantum attack? No. Enlarging the group defends only against classical attacks. Shor’s algorithm’s cost grows polynomially with the size of the problem, so a bigger key or curve makes the eventual quantum attack larger while leaving it feasible, which is why the answer is to replace the algorithm rather than resize it.

What replaces Diffie-Hellman and ECDSA in a post-quantum world? ML-KEM replaces the discrete-log key-exchange algorithms (Diffie-Hellman and ECDH), and ML-DSA, with SLH-DSA as a conservative backup, replaces the discrete-log signature algorithms (ECDSA, Ed25519, DSA). All were finalized by NIST in August 2024, and they rest on lattice and hash-based math that Shor’s algorithm does not solve.

Do I need to understand the discrete logarithm to plan a migration? Not the math itself, but the one takeaway matters: any algorithm labeled DH, ECDH, ECDHE, ECDSA, EdDSA, DSA, or ElGamal has a discrete-log dependency and must be replaced rather than resized. That single mapping turns an inventory finding into a migration decision.

---

Everything here is the map, given freely. When your team needs its own discrete-log footprint found, classified, and sequenced for replacement, that’s what an alignment briefing is for.

Last verified 2026-07-09 · Maintained by Addie LaMarr, LaMarr Labs.