# Discrete logarithm

A discrete logarithm is the exponent x satisfying \( g^{x} = h \) in a finite group G generated by an element g; the discrete logarithm problem is to recover x from g and h. The name comes from the analogy with the ordinary logarithm, since discrete exponentiation obeys \( g^{x+y} = g^{x} \cdot g^{y} \), but the quantity x lives in a finite cyclic group rather than the real numbers. When g does not generate the whole group, a solution exists only for elements of the subgroup generated by g, and it is unique modulo the order of g.<sup>[1](https://www-users.cse.umn.edu/~odlyzko/doc/discretelogs2014.pdf)</sup>

| Key fact | Detail |
|---|---|
| Definition | Given a generator g of a cyclic group G and an element h, find x with \( g^{x} = h \); x is unique modulo ord(g)<sup>[1](https://www-users.cse.umn.edu/~odlyzko/doc/discretelogs2014.pdf)</sup> |
| Cryptographic role | Security assumption of the 1976 Diffie-Hellman key exchange and a large variety of later public-key systems and protocols<sup>[1](https://www-users.cse.umn.edu/~odlyzko/doc/discretelogs2014.pdf)</sup> |
| Generic algorithms | Baby-step giant-step needs \( O(\sqrt{q} \cdot \mathrm{polylog}(q)) \) time and \( O(\sqrt{q}) \) memory; Pollard's rho reaches \( O(\sqrt{q}) \) time with constant memory, for a group of order q<sup>[5](https://www.cl.cam.ac.uk/teaching/2223/Crypto/crypto-slides-2up.pdf)</sup> |
| Finite fields | Index calculus and the Number Field Sieve give subexponential \( L \)-notation algorithms, so finite-field parameters must be large (1024 bits or more for classical security)<sup>[6](https://www.cs.umd.edu/~waa/414-F11/IntroToCrypto.pdf)</sup> |
| Elliptic curves | No subexponential algorithm is known for general elliptic curve groups; parallel Pollard rho is the best practical general attack<sup>[6](https://www.cs.umd.edu/~waa/414-F11/IntroToCrypto.pdf)</sup> |
| Quantum threat | Shor's 1994 algorithm solves discrete logarithms in polynomial time on a quantum computer, in steps polynomial in the input size<sup>[2](https://arxiv.org/abs/quant-ph/9508027)</sup> |
| Computation records | A 795-bit prime-field discrete logarithm was computed in 2019 alongside the RSA-240 factorization; a record in \( \mathbb{F}_{2^{30750}} \) broke the 2014 \( \mathbb{F}_{2^{9234}} \) record<sup>[7](https://arxiv.org/abs/2006.06197)</sup><sup> • </sup><sup>[8](https://arxiv.org/abs/2008.02717)</sup> |
| Standardization | NIST SP 800-186 (February 2023) specifies the elliptic curves recommended for U.S. Government use; NIST plans to deprecate quantum-vulnerable algorithms from its standards by 2035<sup>[3](https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-186.pdf)</sup><sup> • </sup><sup>[10](https://www.nist.gov/news-events/news/2024/08/nist-releases-first-3-finalized-post-quantum-encryption-standards)</sup> |

## Role in cryptography

The first practical public-key cryptosystem, the Diffie-Hellman key exchange published by [Whitfield Diffie](https://www.edgepedia.org/whitfield-diffie) and Martin E. Hellman in 1976 in *IEEE Transactions on Information Theory*, relies for its security on the assumption that discrete logarithms are hard to compute. That intractability hypothesis also underlies a large variety of later public-key systems and protocols.<sup>[1](https://www-users.cse.umn.edu/~odlyzko/doc/discretelogs2014.pdf)</sup> SP 800-56A, NIST's standard for establishing keys, defines discrete-logarithm techniques in both finite-field and elliptic-curve settings, covering multiple Diffie-Hellman and Menezes-Qu-Vanstone (MQV) variants.<sup>[11](https://www.nist.gov/publications/recommendation-pair-wise-key-establishment-schemes-using-discrete-logarithm-1)</sup> In TLS, RFC 7919 defines named finite-field Diffie-Hellman groups (ffdhe2048 through ffdhe8192) that peers negotiate through the Supported Groups extension, replacing ad hoc server-chosen parameters whose structure clients could not verify.<sup>[4](https://www.rfc-editor.org/rfc/rfc7919.html)</sup>

The choice of group matters as much as the size of the group. The Pohlig-Hellman algorithm reduces a discrete logarithm in a group of composite order n to discrete logarithms in cyclic subgroups of prime order \( p_i \), so the difficulty of the problem is governed by the largest prime factor of the group order; a hard instance must be set in a group whose order has a large prime factor.<sup>[1](https://www-users.cse.umn.edu/~odlyzko/doc/discretelogs2014.pdf)</sup><sup> • </sup><sup>[6](https://www.cs.umd.edu/~waa/414-F11/IntroToCrypto.pdf)</sup> For elliptic curves, NIST SP 800-186 requires each recommended curve to have order \( h \cdot n \) with n a large prime and small cofactor h, order different from the field size to avoid anomalous-curve attacks, and embedding degree k at least \( 2^{10} \), because a small embedding degree converts the elliptic curve problem into an ordinary discrete logarithm in \( \mathrm{GF}(q^{k}) \) where index calculus applies.<sup>[3](https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-186.pdf)</sup>

## Classical algorithms

**Generic algorithms.** Methods that use only the group operation apply to any cyclic group. The trivial brute-force search tries all powers of g and takes time up to the group order. Shanks' [baby-step giant-step](https://www.edgepedia.org/baby-step-giant-step) algorithm writes the unknown exponent in a two-digit representation and matches halves of the cycle: it stores \( \sqrt{q} \) giant-step values in a table and then takes baby steps from the target until a match appears, running in \( O(\sqrt{q} \cdot \mathrm{polylog}(q)) \) time with \( O(\sqrt{q}) \) memory. Pollard's rho algorithm reaches the same \( O(\sqrt{q}) \) expected time with constant memory by detecting a collision in a pseudorandom walk, exploiting the birthday paradox.<sup>[5](https://www.cl.cam.ac.uk/teaching/2223/Crypto/crypto-slides-2up.pdf)</sup><sup> • </sup><sup>[16](https://bukittimahtutor.com/mathematics/computational-number-theory-discrete-logarithms-baby-step-giant-step-pollard-rho/)</sup> In the generic group model, square-root complexity is a lower bound for the best broad classical methods, and Victor Shoup proved lower bounds for generic discrete logarithm algorithms.<sup>[16](https://bukittimahtutor.com/mathematics/computational-number-theory-discrete-logarithms-baby-step-giant-step-pollard-rho/)</sup><sup> • </sup><sup>[15](https://cs355.stanford.edu/schedule/cryptanalysis/lecture-6/)</sup>

**Index calculus.** For the multiplicative group of a finite field, algorithms can exploit algebraic structure that a generic group lacks. Index calculus reduces the discrete logarithm problem to finding smooth relations among elements, yielding subexponential running times expressed in \( L \)-notation, \( L_{a,b}(N) = e^{b(\log N)^{a}(\log\log N)^{1-a}} \), which interpolates between polynomial \( L_{0,b} \) and exponential \( L_{1,b} \) complexity. The Number Field Sieve (NFS) is the best known method for finite fields of medium to large characteristic, with four phases: polynomial selection, relation collection, linear algebra, and individual logarithm computation.<sup>[1](https://www-users.cse.umn.edu/~odlyzko/doc/discretelogs2014.pdf)</sup><sup> • </sup><sup>[9](https://arxiv.org/abs/1505.07553)</sup> In fields of small characteristic, a series of breakthroughs in late 2012 and early 2013 culminated in a heuristic quasi-polynomial-time algorithm due to [Antoine Joux](https://www.edgepedia.org/antoine-joux) and colleagues Barbulescu, Gaudry, and Thomé.<sup>[8](https://arxiv.org/abs/2008.02717)</sup>

The practical consequence is a large gap in parameter sizes. Because index calculus applies to \( \mathbb{F}_{q}^{*} \) and reduces the security level to \( (\log_{2} q)^{1/2+o(1)} \) bits, finite-field groups need a much larger q than elliptic curve groups to resist attack; computations in elliptic curve groups cost more per operation, but this is outweighed by the smaller field size they permit.<sup>[12](https://cr.yp.to/papers/safecurves-20240809.pdf)</sup> Textbook guidance states that a hard finite-field discrete logarithm problem requires fields \( \mathbb{F}_{p^{t}} \) with \( p^{t} \ge 2^{1024} \), while for elliptic curves no subexponential algorithms are known except in special cases, so the only practical general attack is parallel Pollard rho, and a subgroup of order about \( 2^{160} \) suffices for 80-bit security.<sup>[6](https://www.cs.umd.edu/~waa/414-F11/IntroToCrypto.pdf)</sup>

**Record computations.** The size of the largest solved instances tracks algorithmic progress. In 2019, researchers announced two results achieved on identical hardware and software: factoring RSA-240, a 795-bit number, and computing a discrete logarithm modulo a 795-bit prime. Their comparison indicated that discrete logarithms are hardly more difficult than factoring equally sized numbers, and thanks to algorithmic variants and well-chosen parameters, both computations cost far less than earlier records would have suggested.<sup>[7](https://arxiv.org/abs/2006.06197)</sup> In small characteristic, a discrete logarithm in \( \mathbb{F}_{2^{30750}} \) broke by a large margin the previous record, set in January 2014 in \( \mathbb{F}_{2^{9234}} \).<sup>[8](https://arxiv.org/abs/2008.02717)</sup> A special number field sieve computation in a 1024-bit prime field took a little over two months of calendar time on an academic cluster, using a trapdoored prime for which detecting the weakness seems out of reach.<sup>[14](https://arxiv.org/abs/1610.02874)</sup>

The individual-logarithm step of NFS has direct attack consequences. In the Logjam attack, revealed in May 2015 against a Diffie-Hellman key exchange in TLS, a seven-day precomputation for relation collection and linear algebra made it possible to compute any given individual discrete logarithm in about one minute for each of two targeted 512-bit prime fields, fast enough for a man-in-the-middle attack.<sup>[9](https://arxiv.org/abs/1505.07553)</sup>

## Special cases and weak groups

Several structured families of groups are deliberately avoided. Supersingular curves and curves with small embedding degree admit a computable mapping from the elliptic curve problem to a finite-field discrete logarithm, giving a subexponential attack; anomalous curves over a prime field, where the group order equals p, fall to an algorithm requiring \( O(\log p) \) elliptic curve operations; and binary curves over \( \mathbb{F}_{2^{n}} \) with composite n are exposed to Weil descent attacks.<sup>[6](https://www.cs.umd.edu/~waa/414-F11/IntroToCrypto.pdf)</sup> Pairing-based constructions inherit the same exposure: a security evaluation of standardized pairing-friendly curves found that the BN256 curves recommended by SM9 and a previous ISO/IEC standard offer only 99.92 bits of security, well below the intended 128-bit level.<sup>[13](https://arxiv.org/abs/2309.04693)</sup>

## The quantum threat

Peter W. Shor, then at [Bell Labs](https://www.edgepedia.org/bell-labs) and later a professor at MIT, showed in 1994 that a hypothetical quantum computer can solve both integer factorization and discrete logarithms with efficient randomized algorithms taking a number of steps polynomial in the input size, such as the number of digits of the integer to be factored; both problems were generally thought to be hard on a classical computer and had been used as the basis of several proposed cryptosystems.<sup>[2](https://arxiv.org/abs/quant-ph/9508027)</sup> The algorithm also works for elliptic curve groups: Proos and Zalka reckoned that roughly 1000 qubits would suffice on a quantum computer to crack a 160-bit elliptic curve cryptographic key, whereas factoring an RSA modulus of 1024 bits—equivalent in security—would need about 2000 qubits.<sup>[17](https://arxiv.org/abs/quant-ph/0301141)</sup>

Because [Shor's algorithm](https://www.edgepedia.org/shors-algorithm) defeats the discrete logarithm assumption itself, the response has been to move public-key cryptography to problems with no known efficient quantum algorithms. NIST began selecting quantum-resistant algorithms in a public competition-like process in 2016 and in August 2024 released its first three finalized post-quantum standards: [FIPS 203](https://www.edgepedia.org/fips-203) (ML-KEM, for general encryption), [FIPS 204](https://www.edgepedia.org/fips-204) (ML-DSA, for digital signatures), and FIPS 205 (SLH-DSA, a backup signature method).<sup>[10](https://www.nist.gov/news-events/news/2024/08/nist-releases-first-3-finalized-post-quantum-encryption-standards)</sup> Under the transition timeline in NIST IR 8547, NIST will deprecate and ultimately remove quantum-vulnerable algorithms, including discrete-logarithm-based ones, from its standards by 2035, with high-risk systems transitioning earlier.<sup>[10](https://www.nist.gov/news-events/news/2024/08/nist-releases-first-3-finalized-post-quantum-encryption-standards)</sup><sup> • </sup><sup>[18](https://www.nist.gov/pqcrypto)</sup>

## References

1. [Antoine Joux, Andrew Odlyzko, and Cécile Pierrot. The Past, evolving Present and Future of Discrete Logarithm.](https://www-users.cse.umn.edu/~odlyzko/doc/discretelogs2014.pdf)
2. [Peter W. Shor. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. arXiv:quant-ph/9508027.](https://arxiv.org/abs/quant-ph/9508027)
3. [NIST SP 800-186. Recommendations for Discrete Logarithm-based Cryptography: Elliptic Curve Domain Parameters (February 2023).](https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-186.pdf)
4. [D. Gillmor. RFC 7919: Negotiated Finite Field Diffie-Hellman Ephemeral Parameters for TLS (August 2016).](https://www.rfc-editor.org/rfc/rfc7919.html)
5. [University of Cambridge. Cryptography course slides (2022-23).](https://www.cl.cam.ac.uk/teaching/2223/Crypto/crypto-slides-2up.pdf)
6. [Nigel Smart. Introduction to Cryptography, Chapter 13: Discrete Logarithms (course text, University of Maryland mirror).](https://www.cs.umd.edu/~waa/414-F11/IntroToCrypto.pdf)
7. [Boudot, Gaudry, Guillevic, Heninger, Thomé, Zimmermann. Comparing the difficulty of factorization and discrete logarithm: a 240-digit experiment. arXiv:2006.06197.](https://arxiv.org/abs/2006.06197)
8. [Gaudry, Kohel, Leroux. Computation of a 30750-Bit Binary Field Discrete Logarithm. arXiv:2008.02717.](https://arxiv.org/abs/2008.02717)
9. [Grémy, Thomé. Computing Individual Discrete Logarithms Faster in GF(p^n) with the NFS-DL Algorithm. arXiv:1505.07553.](https://arxiv.org/abs/1505.07553)
10. [NIST Releases First 3 Finalized Post-Quantum Encryption Standards (August 13, 2024).](https://www.nist.gov/news-events/news/2024/08/nist-releases-first-3-finalized-post-quantum-encryption-standards)
11. [NIST SP 800-56Ar3. Recommendation for Pair-Wise Key-Establishment Schemes Using Discrete Logarithm Cryptography (2018).](https://www.nist.gov/publications/recommendation-pair-wise-key-establishment-schemes-using-discrete-logarithm-1)
12. [Daniel J. Bernstein and Tanja Lange. SafeCurves paper (2024 version).](https://cr.yp.to/papers/safecurves-20240809.pdf)
13. [Security Analysis of Pairing-based Cryptography. arXiv:2309.04693.](https://arxiv.org/abs/2309.04693)
14. [Kleinjung, Wesolowski et al. A kilobit hidden SNFS discrete logarithm computation. arXiv:1610.02874.](https://arxiv.org/abs/1610.02874)
15. [Stanford CS 355, Lecture 6: Attacks on Groups.](https://cs355.stanford.edu/schedule/cryptanalysis/lecture-6/)
16. [Bukit Timah Tutor. Computational Number Theory 6: Discrete Logarithms, Baby-Step Giant-Step and Pollard Rho.](https://bukittimahtutor.com/mathematics/computational-number-theory-discrete-logarithms-baby-step-giant-step-pollard-rho/)
17. [Proos, Zalka. Shor's discrete logarithm quantum algorithm for elliptic curves. arXiv:quant-ph/0301141.](https://arxiv.org/abs/quant-ph/0301141)
18. [NIST Post-Quantum Cryptography project page.](https://www.nist.gov/pqcrypto)

---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Numbers and algebra › Number theory › Computational and probabilistic number theory › Discrete logarithm and cyclic-group algorithms*

*Initially written Sep 17, 2026 · Reviewed: Sep 30, 2026; Oct 15, 2026 · Edited: Sep 30, 2026; Oct 15, 2026 · Last review: Oct 15, 2026*

*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*

License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license