Discrete logarithm problem

In mathematics, a discrete logarithm is an integer k solving the equation bk = g, where b and g are elements of a group. Discrete logarithms are thus the group-theoretic analogue of ordinary logarithms, which solve the same equation for real numbers b and g, where b is the base of the logarithm and g is the value whose logarithm is being taken.

Computing discrete logarithms is believed to be difficult. No efficient general method for computing discrete logarithms on conventional computers is known, and several important algorithms in public-key cryptography base their security on the assumption that the discrete logarithm problem has no efficient solution.

Example

Discrete logarithms are perhaps simplest to understand in the group (Zp)×. This is the group of multiplication modulo the prime p. its elements are congruence classes modulo p, and the group product of two elements may be obtained by ordinary integer multiplication of the elements followed by reduction modulo p.

The kth power of one of the numbers in this group may be computed by finding its kth power as an integer and then finding the remainder after division by p. This process is called modular exponentiation. For example, consider (Z17)×. To compute 34 in this group, compute 34 = 81, and then divide 81 by 17, obtaining a remainder of 13. Thus 34 = 13 in the group (Z17)×.

The discrete logarithm is just the inverse operation. For example, consider the equation 3k ≡ 13 (mod 17) for k. From the example above, one solution is k = 4 is a solution, but it is not the only solution. Since 316 ≡ 1 (mod 17) — as follows from Fermat's little theorem — it also follows that if n is an integer then 34+16n ≡ 34 × (316)n ≡ 13 × 1n ≡ 13 (mod 17). Hence the equation has infinitely many solutions of the form 4 + 16n. Moreover, since 16 is the smallest positive integer m satisfying 3m ≡ 1 (mod 17), i.e. 16 is the order of 3 in (Z17)×, these are the only solutions. Equivalently, the set of all possible solutions can be expressed by the constraint that k ≡ 4 (mod 16).

Definition

In general, let G be any group, with its group operation denoted by multiplication. Let b and g be any elements of G. Then any integer k that solves bk = g is termed a discrete logarithm (or simply logarithm, in this context) of g to the base b. We write k = logb g. Depending on b and g, it is possible that no discrete logarithm exists, or that more than one discrete logarithm exists. Let H be the subgroup of G generated by b. Then H is a cyclic group, and logb g exists for all g in H. If H is infinite, then logb g is also unique, and the discrete logarithm amounts to a group isomorphism

\log_b \colon H \rightarrow \mathbf{Z}.

On the other hand, if H is finite of size n, then logb g is unique only up to congruence modulo n, and the discrete logarithm amounts to a group isomorphism

\log_b\colon H \rightarrow \mathbf{Z}_n,

where Zn denotes the ring of integers modulo n. The familiar base change formula for ordinary logarithms remains valid: If c is another generator of H, then

\log_c (g) = \log_c (b) \cdot \log_b (g).

Algorithms

List of unsolved problems in computer science
Can the discrete logarithm be computed in polynomial time on a classical computer?

No efficient classical algorithm for computing general discrete logarithms logb 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.[1]

More sophisticated algorithms exist, usually inspired by similar algorithms for integer factorization. These algorithms run faster than the naive algorithm, some of them linear in the square root of the size of the group, and thus exponential in half the number of digits in the size of the group. However none of them runs in polynomial time (in the number of digits in the size of the group).

Comparison with integer factorization

While computing discrete logarithms and factoring integers 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 used to construct various cryptographic systems.

Cryptography

There exist groups for which computing discrete logarithms is apparently difficult. In some cases (e.g. large prime order subgroups of groups (Zp)×) there is not only no efficient algorithm known for the worst case, but the average-case complexity can be shown to be about as hard as the worst case using random self-reducibility.

At the same time, the inverse problem of discrete exponentiation is not difficult (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 (Zp)× (e.g. ElGamal encryption, Diffie–Hellman key exchange, and the Digital Signature Algorithm) and cyclic subgroups of elliptic curves over finite fields (see elliptic curve cryptography).

References

This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.