🔐Discrete Logarithm

NEW

Also known as: DLP

The computational problem of finding an exponent x such that g^x equals a given group element, fundamental to several cryptographic schemes.

DESCRIPTION

The discrete logarithm problem asks, given a generator g of a finite group and an element h, for k such that g^k = h. Its presumed difficulty in suitable groups underlies Diffie–Hellman key exchange and ElGamal encryption. Variants exist over finite fields and elliptic curves, with different algorithmic complexities. Attacks include Pollard’s rho and index calculus; parameter choices are critical to security. It is often contrasted with integer factorization as a separate cryptographic hardness assumption.

ALTERNATIVE DEFINITIONS

Wikipedia

In mathematics, the discrete logarithm is an integer k given a number a and a finite group G such that a^k is equal to another number b.

Introduces the problem in group-theoretic terms.

Source

NIST SP 800-56A Rev. 3

The discrete logarithm (DL) problem is: given Q = xP and P, determine the integer x.

Presents the elliptic-curve variant of the DL problem used in key establishment.

Source

IETF RFC 4949

Discrete logarithm problem (DLP): Given elements α and β of a finite cyclic group, find an integer x such that α^x = β.

Concise, group-agnostic statement in a security glossary.

Source

RELATED TERMS

Diffie–Hellman Key Exchange Elliptic Curve Cryptography Galois Field Cyclic Group Elgamal Pollard’s Rho Index Calculus Hard Problem Modular Exponentiation Digital Signature Algorithm Cryptanalysis Hardness Assumption RSA

COMPETING TERMS

Integer Factorization

KNOWLEDGE AREAS

Mathematics Data Security

TARGET AUDIENCE

Cybersecurity Engineer Security Architect Chief Information Security Officer Software Developer Data Scientist Cloud Architect

EXTERNAL SOURCES

• Wikipedia - Discrete logarithm
• NIST - Defines DL problem in key establishment
• IETF - Internet Security Glossary entry for DLP
• Wolfram MathWorld - Background and algorithms for DLP

TOP QUESTIONS

Why are Discrete Logarithms important?

They underpin security of Diffie–Hellman and ElGamal; hardness assumptions enable practical public-key cryptography.

Category: Relevancy

Which groups are used for Discrete Logarithms?

Multiplicative groups of finite fields and elliptic curve groups, each with distinct security and performance characteristics.

Category: Definition

What is a common mistake in DLP parameter selection?

Choosing small or special-field sizes that enable sub-exponential attacks like index calculus.

Category: Mistakes

How does DLP compare to Integer Factorization?

They are distinct hard problems; some cryptosystems rely on DLP, others on factoring, providing diversified assumptions.

Category: Alternatives

What are practical DLP attacks?

Pollard’s rho for generic groups, number field sieve variants for finite fields, and special-structure attacks.

Category: Risk

Is DLP quantum-safe?

No; Shor’s algorithm solves DLP efficiently on a large-scale quantum computer, motivating post-quantum schemes.

Category: Risk

Where is DLP used in protocols?

In Diffie–Hellman key exchange, ElGamal encryption/signatures, and many ECC-based standards.

Category: Application

How to choose secure DLP parameters?

Follow standards specifying group sizes and curves, and avoid fields with known special-structure attacks.

Category: HowTo

Where to learn more about DLP?

Consult NIST SP 800-56A and MathWorld for definitions, context, and algorithms.

Category: GettingStarted