Papex

Open problem · Computer science · Open

Complexity of the discrete logarithm

Can a classical computer compute discrete logarithms in polynomial time?

Summary

Given g and gˣ in a group such as the integers modulo a prime, the task is to recover x. Diffie–Hellman key exchange and related schemes rely on this being hard, yet no proof shows that a fast classical algorithm cannot exist.

Why it is open

In a cyclic group generated by g, the discrete logarithm of h is a number x with h = g^x, and solving the discrete logarithm problem means recovering x from g^x [3]. Diffie–Hellman key exchange, the first practical public-key system to be published, relies on this being hard, as do many later systems [3]; whether any function at all is hard to invert in this way is the subject of the Papex page One-way functions. The Wikipedia list of unsolved problems in computer science, which sets this page's status, asks the question for "a classical (non-quantum) computer" [10], because Peter Shor gave a polynomial-time algorithm for a quantum one [2].

The question is several questions, because the answer depends on how the group's elements are represented [1]. In 2014 Antoine Joux, Andrew Odlyzko and Cécile Pierrot wrote that the problem "is still considered to be hard" in general, in particular for "the multiplicative group of finite fields with medium to large characteristic and for the additive group of a general elliptic curve" [3]. (A finite field has p^n elements for a prime p, its characteristic [3].) For fields of small characteristic the problem has turned out to be much easier [5, 7].

Two facts shape what a resolution could look like. A decision version, asking whether h = g^x for some x up to a given bound, is essentially as hard as computing x and lies in both NP and co-NP [3]; the relation between these two classes is the subject of the Papex page NP versus co-NP. And within one group, if the problem is easy on average it is easy in the worst case, by a randomisation argument [3]. A resolution would be a classical polynomial-time algorithm for a family of groups, or a proof that none exists; no prize or committee sets the bar. Victor Shoup proved a lower bound for "generic" algorithms, which use nothing but the group operation [1].

What is known

Generic algorithms (1978–1997). A generic algorithm treats group elements as arbitrary labels and works only through the group operation [1]. Given the factorisation of the group order, the algorithm of Stephen Pohlig and Martin Hellman reduces the problem to subgroups of prime order, and John Pollard's rho method needs about the square root of the group order in operations and almost no memory; combined, they take about √p operations, where p is the largest prime dividing the order [3]. Shoup proved in 1997 that any generic algorithm needs Ω(√p) group operations, matching these methods [1]. He noted that index-calculus methods for the multiplicative group of integers modulo a prime are not generic, so his results "have no bearing on such algorithms", whereas for elliptic curves "the only known algorithms for discrete logarithms are generic" [1].

Index calculus and the number field sieve (1979–2021). Index-calculus algorithms collect relations among the logarithms of a set of "small" elements, solve the resulting sparse linear system, and then express any element through that set [3]. Their running times are written L_Q(α, c) = exp((c + o(1)) (log Q)^α (log log Q)^(1−α)) for a field of Q elements: the closer α is to 0, the closer to polynomial, and the closer to 1, the closer to exponential [3]. Don Coppersmith gave a heuristic L(1/3) algorithm for characteristic 2 in 1984, and by 2006 the number field sieve and the function field sieve together covered all finite fields with heuristic L(1/3) algorithms, with constant c = (64/9)^(1/3) for large characteristic [3]. In 2020 Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé and Paul Zimmermann reported a discrete logarithm modulo a 795-bit prime, about 3,200 core-years of computation, alongside the factorisation of a 795-bit number; at this size they found the discrete logarithm only about three times harder [6] (see Complexity of integer factorisation). A 2021 paper still called it the discrete logarithm record for prime fields [7].

Small characteristic (2013–2026). In 2013 Joux described an algorithm of heuristic complexity L(1/4 + o(1)) for fields of small characteristic [4]. Razvan Barbulescu, Gaudry, Joux and Thomé then gave a heuristic quasi-polynomial algorithm, of complexity n^O(log n) for a field whose size has n bits; this is smaller than any L(ε), but "remains super-polynomial in the size of the input" [5]. In a paper published in 2021, Robert Granger, Thorsten Kleinjung, Arjen Lenstra, Benjamin Wesolowski and Jens Zumbrägel reported a discrete logarithm in the field of 2^30750 elements, far beyond the January 2014 record of 2^9234; it made essential use of the elimination step of another quasi-polynomial algorithm, by Granger, Kleinjung and Zumbrägel, and took about 2,900 core-years, which they call comparable to the effort for the 795-bit prime-field record [7]. Kleinjung and Wesolowski proved that the problem can be solved in quasi-polynomial expected time in fields of fixed characteristic, in expected time (pn)^(2 log₂ n + O(1)) for a field of p^n elements; their paper appeared in 2022 after a 2019 preprint [8]. In a 2026 journal paper, Guido Lido gave a provably quasi-polynomial algorithm for fields whose characteristic is logarithmic in their size, partly following Barbulescu and colleagues and using a presentation of the field based on elliptic curves [9].

Elliptic curves (1997–2014). Subexponential index-calculus algorithms exist for many discrete logarithm problems; in 2014 Joux and colleagues called elliptic curves "the one notable exception": for general curves nothing better than generic algorithms was known, and the best known algorithms took exponential time [3]. For some special classes of curves the problem can be transferred to a finite field or to a curve of higher genus, and curves over extension fields admit decomposition methods based on Igor Semaev's summation polynomials, whose behaviour for large extension degrees is "much harder to predict" [3].

Quantum context (1994–1997). Shor's algorithm computes discrete logarithms on a "hypothetical quantum computer" in a number of steps polynomial in the input size [2], and works for any group whose operation can be computed efficiently [3].

Main approaches

Faster sieving for large characteristic. Improve the number field sieve for prime fields and fields of medium and large characteristic [3]. Strongest evidence: new variants for medium and high characteristic in 2013 and 2014 [3]; careful parameter choices made the 795-bit computation cheaper than extrapolation from earlier records suggested [6]; and Joux and colleagues write that L(1/3) "no longer seems to be a natural bound" [3]. Main difficulty: the small-characteristic methods "deeply rely on specific properties of polynomials which do not seem readily adaptable to numbers" [3].

Descent in small characteristic. Push the quasi-polynomial methods further [3]. Strongest evidence: heuristic quasi-polynomial algorithms [5], since proved for fixed and for small characteristic [8, 9], and the 30,750-bit computation [7]. Main difficulty: the running time "remains super-polynomial" [5]; Joux and colleagues list a better exponent and "the search for a polynomial time algorithm" among the open directions [3].

Index calculus for elliptic curves. Find relations among curve points, for example with summation polynomials [3]. Strongest evidence: index-calculus algorithms for curves of genus at least 3, and decomposition methods for elliptic curves over some extension fields [3]. Main difficulty: Joux and colleagues write that "the most difficult challenge for discrete logarithms is probably the search for a subexponential algorithm that would apply to general elliptic curves defined over large characteristic fields" [3].

Lower bounds in restricted models. Prove that a class of algorithms cannot beat a given running time [1]. Strongest evidence: Shoup's Ω(√p) bound, which the best generic algorithms match [1, 3]. Main difficulty: the bound has no bearing on index calculus [1], and the generic group model shares a weakness of the random oracle model: some protocols that are secure in it cannot be securely instantiated [3].

Open sub-questions

  1. The quasi-polynomial exponent. Can the exponent 2 log₂ n in Kleinjung and Wesolowski's bound (pn)^(2 log₂ n + O(1)) for fixed characteristic be lowered by a constant factor, or replaced by a slower-growing function of n [3, 8]?
  2. Larger characteristic. Lido's proof covers fields whose characteristic is logarithmic in their size [9]; up to which faster-growing characteristic, below the range where the number field sieve is used, can a quasi-polynomial running time be reached, heuristically or provably [3, 5, 9]?
  3. Provable L(1/3) for prime fields. The first index-calculus algorithms for prime fields ran in time L(1/2) and were given provable versions; can a rigorous L(1/3, c) bound be proved for prime fields [3]?
  4. Factoring against discrete logarithms. Does the factor of about three between the 795-bit discrete logarithm and a factorisation of the same size stay stable for larger safe primes [6]?
  5. Summation polynomials. For elliptic curves over fields of 2^p elements with p prime, does index calculus with summation polynomials beat generic algorithms asymptotically [3]?

Work on this in Papex

If you have a testable answer to one of the sub-questions above, you can draft it as a private hypothesis in Papex, or prepare the draft from Claude or ChatGPT with the Papex connector. You review the exact version, sign it and decide whether to publish it; a public record that names this problem is listed on this page. A Papex record shows who signed which version and when. It is not peer review and does not mean the hypothesis is correct.

Key references

  1. Shoup, V. (1997). Lower bounds for discrete logarithms and related problems. In Advances in Cryptology – EUROCRYPT '97, Lecture Notes in Computer Science, Springer, 256–266. 10.1007/3-540-69053-0_18 · Checked 15 Oct 2026
  2. Shor, P. W. (1997). Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing 26(5), 1484–1509. 10.1137/S0097539795293172 · Checked 15 Oct 2026
  3. Joux, A., Odlyzko, A. & Pierrot, C. (2014). The past, evolving present, and future of the discrete logarithm. In Ç. K. Koç (ed.), Open Problems in Mathematics and Computational Science, Springer, 5–36. 10.1007/978-3-319-10683-0_2 · Checked 15 Oct 2026
  4. Joux, A. (2014). A new index calculus algorithm with complexity L(1/4+o(1)) in small characteristic. In Selected Areas in Cryptography – SAC 2013, Lecture Notes in Computer Science, Springer, 355–379. 10.1007/978-3-662-43414-7_18 · Checked 15 Oct 2026
  5. Barbulescu, R., Gaudry, P., Joux, A. & Thomé, E. (2014). A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic. In Advances in Cryptology – EUROCRYPT 2014, Lecture Notes in Computer Science, Springer, 1–16. 10.1007/978-3-642-55220-5_1 · Checked 15 Oct 2026
  6. Boudot, F., Gaudry, P., Guillevic, A., Heninger, N., Thomé, E. & Zimmermann, P. (2020). Comparing the difficulty of factorization and discrete logarithm: a 240-digit experiment. In Advances in Cryptology – CRYPTO 2020, Lecture Notes in Computer Science, Springer, 62–91. 10.1007/978-3-030-56880-1_3 · Checked 15 Oct 2026
  7. Granger, R., Kleinjung, T., Lenstra, A. K., Wesolowski, B. & Zumbrägel, J. (2021). Computation of a 30750-bit binary field discrete logarithm. Mathematics of Computation, published online 16 July 2021. 10.1090/mcom/3669 · Checked 15 Oct 2026
  8. Kleinjung, T. & Wesolowski, B. (2022). Discrete logarithms in quasi-polynomial time in finite fields of fixed characteristic. Journal of the American Mathematical Society 35(2), 581–624 (published online 8 September 2021). 10.1090/jams/985 · Checked 15 Oct 2026
  9. Lido, G. (2026). A provably quasi-polynomial algorithm for the discrete logarithm problem in finite fields of small characteristic. Finite Fields and Their Applications 111, 102753. 10.1016/j.ffa.2025.102753 · Checked 15 Oct 2026
  10. Wikipedia. List of unsolved problems in computer science (revision of 15 September 2026). Source · Checked 15 Oct 2026

Page reviewed 15 Oct 2026

Source

Open, as listed by Wikipedia · Unsolved problems in computer science. Checked 08 Oct 2026.

The status is the source’s. Papex does not decide whether a problem is solved.

Records on this problem

No public record addresses this problem yet.

More in Computing