# Discrete logarithm

In abstract algebra and its applications, the **discrete logarithms** are defined in group theory in analogy to ordinary logarithms.

Discrete logarithms are perhaps simplest to understand in the group (**Z**_{p})^{×}. This is the set {1, …, *p* − 1} under multiplication modulo the prime *p*. If we want to find the *k*th power of one of the numbers in this group, called *discrete exponentiation*, we do so by finding its *k*th power as an integer and then finding the remainder after division by *p*. For example, 3 to the 5th power is 243, and when we divide 243 by 7 the remainder is 5; thus, 3^{5} in the group (**Z**_{7})^{×} is 5. Once we have discrete exponentiation, discrete logarithm is just the inverse operation: given that 3^{k} ≡ 5 (mod 7), what is the smallest *k* that makes this true?

More generally, let *G* be a finite cyclic group with *n* elements. We assume that the group is written multiplicatively. Let *b* be a generator of *G*; then every element *x* of *G* can be written in the form *x* = *b*^{k} for some integer *k*. Furthermore, any two such integers representing *x* will be congruent modulo *n*. We can thus define a function

**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \log_b:\ G\ \rightarrow\ \mathbf{Z}_n}**

(where **Z**_{n} denotes the ring of integers modulo *n*) by assigning to *x* the congruence class of *k* modulo *n*. This function is a group isomorphism, called the discrete logarithm to base *b*.

The familiar base change formula for ordinary logarithms remains valid: if *c* is another generator of *G*, then we have

**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \log_c (x) = \log_c(b) \cdot \log_b(x).}**

## Practical uses

For some groups, computing discrete logarithms is believed to be difficult, while the inverse problem of discrete exponentiation is not (it can be efficiently computed for example using exponentiation by squaring). This asymmetry is exploited in some applications in cryptography. The problem of how to extract general discrete logarithms is known as the **generalized discrete logarithm problem** (**GDLP**), and there is no known efficient algorithm.

Popular choices for *G* in cryptography are the cyclic groups (**Z**_{p})^{×}; see ElGamal encryption, Diffie-Hellman key exchange, and the Digital Signature Algorithm.

Newer cryptography applications use discrete logarithms in cyclic subgroups of elliptic curves over finite fields. See elliptic curve cryptography.

## Algorithms for finding discrete logarithms

Many of these algorithms are analogous to integer factorization algorithms. Integer factorization is another mathematically hard problem that finds applications in cryptography.

- Trial multiplication
- Baby-step giant-step
- Pollard's rho algorithm for logarithms
- Pohlig-Hellman algorithm
- Index calculus algorithm

de:Diskreter Logarithmus fr:Logarithme discret pl:Logarytm dyskretny