# Discrete logarithm

### From Wikipedia, the free encyclopedia

In mathematics, specifically in abstract algebra and its applications, **discrete logarithms** are group-theoretic analogues of ordinary logarithms. In particular, an ordinary logarithm log_{a}(*b*) is a solution of the equation *a*^{x} = *b* over the real or complex numbers. Similarly, if *g* and *h* are elements of a finite cyclic group *G* then a solution *x* of the equation *g*^{x} = *h* is called a discrete logarithm to the base *g* of *h* in the group *G*.

## Contents |

## [edit] Example

Discrete logarithms are perhaps simplest to understand in the group (**Z**_{p})^{×}. This is the set of congruence classes {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, we can do so by finding its *k*th power as an integer and then finding the remainder after division by *p*. This process is called *discrete exponentiation*. For example, consider (**Z**_{17})^{×}. To compute 3^{4} in this group, we first compute 3^{4} = 81, and then we divide 81 by 17, obtaining a remainder of 13. Thus 3^{4} = 13 in the group (**Z**_{17})^{×}.

*Discrete logarithm* is just the inverse operation. For example, take the equation 3^{k} ≡ 13 (mod 17) for *k*. As shown above *k*=4 is a solution, but it is not the only solution. Since 3^{16} ≡ 1 (mod 17) it also follows that if *n* is an integer then 3^{4+16 n} ≡ 13 × 1^{n} ≡ 13 (mod 17). Hence the equation has infinitely many solutions of the form 4 + 16*n*. Moreover, since 16 is the smallest positive integer *m* satisfying 3^{m} ≡ 1 (mod 17), i.e. 16 is the order of 3 in (**Z**_{17})^{×}, these are the only solutions. Equivalently, the solution can be expressed as *k* ≡ 4 (mod 16).

## [edit] Definition

In general, 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 *g* of *G* can be written in the form *g* = *b*^{k} for some integer *k*. Furthermore, any two such integers representing *g* will be congruent modulo *n*. We can thus define a function

(where **Z**_{n} denotes the ring of integers modulo *n*) by assigning to *g* 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

## [edit] Algorithms

No efficient algorithm for computing general discrete logarithms log_{b}*g* is known. The naive algorithm is to raise *b* to higher and higher powers *k* until the desired *g* is found; this is sometimes called *trial multiplication*. This algorithm requires running time linear in the size of the group *G* and thus exponential in the number of digits in the size of the group. There exists an efficient quantum algorithm due to Peter Shor however (http://arxiv.org/abs/quant-ph/9508027).

More sophisticated algorithms exist, usually inspired by similar algorithms for integer factorization. These algorithms run faster than the naive algorithm, but none of them runs in polynomial time (in the number of digits in the size of the group).

- Baby-step giant-step
- Pollard's rho algorithm for logarithms
- Pollard's lambda algorithm (aka Pollard's kangaroo algorithm)
- Pohlig-Hellman algorithm
- Index calculus algorithm
- Number field sieve
- Function field sieve

## [edit] Comparison with integer factorization

While the problem of computing discrete logarithms and the problem of integer factorization are distinct problems they share some properties

- both problems are difficult (no efficient algorithms are known for non-quantum computers),
- for both problems efficient algorithms on quantum computers are known,
- algorithms from one problem are often adapted to the other, and
- the difficulty of both problems has been exploited to construct various cryptographic (code) systems.

## [edit] Cryptography

Computing discrete logarithms is apparently difficult. Not only is no efficient algorithm known for the worst case, but the average-case complexity can be shown to be at least as hard as the worst case using random self-reducibility.

At the same time, the inverse problem of discrete exponentiation is not (it can be computed efficiently using exponentiation by squaring, for example). This asymmetry is analogous to the one between integer factorization and integer multiplication. Both asymmetries have been exploited in the construction of cryptographic systems.

Popular choices for the group *G* in discrete logarithm 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.

## [edit] See also

## [edit] References

- Richard Crandall; Carl Pomerance. Chapter 5,
*Prime Numbers: A computational perspective*, 2nd ed., Springer. - Douglas R. Stinson.
*Cryptography: Theory and Practice*, CRC Press, 2002.