Definition:Discrete Logarithm Problem

Definition

Let $g$ be a generator of a cyclic group $G$.

The discrete logarithm problem is to find a value of the integer $x$ in the equation:

$y = g^x$

for a given $y \in G$.

It is usual for $G$ to be the multiplicative group of a finite field.

Also see

• Results about the discrete logarithm problem can be found here.

Historical Note

The discrete logarithm problem is known to be a "very difficult" problem to solve for a large cyclic group.

Hence its usefulness in the field of cryptography, where, for example, the Diffie-Hellman-Merkle key exchange technique utilises this very difficulty.

Linguistic Note

The discrete logarithm problem is so called because its solution is equivalent to the problem of solving $y = e^x$ where $x$ and $y$ are real numbers and whose solution is $x = \ln y$.

Sources

• 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): discrete logarithm problem