Discrete Logarithm

mathematics number-theory cryptography

Definition

Discrete Logarithm

Let $G$ be a finite cyclic group of order $q$ with generator $g$. For an element $h\in G$, the discrete logarithm of $h$ with respect to base $g$ is the unique integer $x\in \{0,1,\dots ,q-1\}$ such that

$$g^x=h$$

The discrete logarithm problem is to find $x$ given $g$ and $h$.

Cryptographic Significance

Computational Hardness

For suitably chosen groups (e.g. large prime-order subgroups of ${\mathbb{Z}}_p^{\ast }$ or elliptic curve groups), no efficient classical algorithm is known for computing discrete logarithms. This hardness assumption underlies the security of Diffie-Hellman and ElGamal.