Discrete logarithm

Definition

Let $G$ be a finite cyclic group 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 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 uses this fact.

Reading path

To understand this page from the ground up, read these 9 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Divisibility definition
Congruence modulo n definition
Greatest common divisor definition
Coprime integers definition
Euler's totient function definition
Euler's theorem statement
Multiplicative order definition
Primitive root modulo n definition
Discrete logarithm definition

Where this leads

1 page builds on this one.

Diffie–Hellman key exchange

Tag	`09B4X51J09`
URI	`m2://09B4X51J09`
Aliases	`index`
Kind	definition
Writing	W1 stated
MSC	11A07
Defines	Discrete logarithm
Uses	Primitive root modulo n

Discrete logarithm

Definition

Remarks

Reading path

Where this leads

Further reading

What this page needs for W2

What links here

Used by