Encyclopedia > Discrete logarithm

  Article Content

Discrete logarithm

Discrete logarithms are defined in group theory in analogy to ordinary logarithms.

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 = bk for some integer k; furthermore any two such integers representing x will be congruent modulo n. We can thus define a function

logb : GZn
(where Zn 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

logc(x) = logc(b) logb(x).

For some groups, computing discrete logarithms is believed to be difficult, while the inverse problem of discrete exponentiation is not; this asymmetry is exploited in some applications in cryptography. Popular choices for G in cryptography are the cyclic groups (Zp)× (consisting of the number {1,...,p-1} under multiplication modulo the prime p); see ElGamal discrete log cryptosystem, Diffie-Hellman key exchange and the Digital Signature Algorithm.

The Pohlig-Hellman algorithm[?] can be used to compute discrete logarithms in these groups if p-1 is a product of small primes, so this should be avoided in those applications. The index calculus[?] is another method to compute discrete logarithms in these groups, as is the birthday attack.

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

All Wikipedia text is available under the terms of the GNU Free Documentation License

  Search Encyclopedia

Search over one million articles, find something about almost anything!
  Featured Article
Great River, New York

... is spread out with 29.0% under the age of 18, 5.0% from 18 to 24, 29.0% from 25 to 44, 24.2% from 45 to 64, and 12.7% who are 65 years of age or older. The median ...

This page was created in 38.2 ms