---
tag: 09B4X51J09
kind: definition
name: Discrete logarithm
aliases: [index]
msc: [11A07]
defines: 0HJHYMGN3C
uses: [0KM2CJ80G7]
sources:
  - url: https://en.wikipedia.org/wiki/Discrete_logarithm
    locator: Definition
---

## Definition

Let $G$ be a finite cyclic [[group|G5S1M9]] of order $N$, with a generator $g$.
For each $h \in G$, the discrete logarithm of $h$ to the base $g$ is the unique integer $k$ with $0 \le k < N$ such that $g^k = h$.
The notation is $k = \log_g h$.

## Remarks

In elementary number theory, $G = (\mathbb{Z}/n\mathbb{Z})^\times$ and $g$ is a [[primitive root|0KM2CJ80G7]] modulo $n$. Then $\log_g a$ is also called the index of $a$, and $N = \varphi(n)$.
The rule $\log_g (h_1 h_2) \equiv \log_g h_1 + \log_g h_2 \pmod N$ holds, as for ordinary logarithms.
For example, $3$ is a primitive root modulo $7$, and $3^4 = 81 \equiv 4 \pmod 7$. So $\log_3 4 = 4$ modulo $7$.
No efficient general algorithm to compute discrete logarithms is known. The [[Diffie–Hellman key exchange|01TKKESHSB]] uses this fact.

## Explanations

### L1 human

[[Modular exponentiation|04DR5PM25N]] computes $g^k \bmod p$ from $k$. The discrete logarithm goes back from the result to $k$.
For small numbers, a table of powers is enough. For numbers with hundreds of digits, the problem seems very hard.