Discrete logarithm

thumb|Discrete logarithm modulo 5, with base 2.

In mathematics, for given real numbers <math>a</math> and <math>b</math>, the logarithm <math>\log_b(a)</math> is a number <math>x</math> such that <math>b^x = a</math>. The discrete logarithm generalizes this concept to a cyclic group. A simple example is the group of integers modulo a prime number (such as 5) under modular multiplication of nonzero elements.

For instance, take <math>b = 2</math> in the multiplicative group modulo 5, whose elements are <math>{1, 2, 3, 4}</math>. Then:

<math display="block">2^1 = 2,\quad 2^2 = 4,\quad 2^3 = 8 \equiv 3 \pmod{5},\quad 2^4 = 16 \equiv 1 \pmod{5}.</math>

The powers of 2 modulo 5 cycle through all nonzero elements, so discrete logarithms exist and are given by:

More generally, in any group <math>G</math>, powers <math>b^k</math> can be defined for all integers <math>k</math>, and the discrete logarithm <math>\log_b(a)</math> is an integer <math>k</math> such that <math>b^k=a</math>. In arithmetic modulo an integer <math>m</math>, the more commonly used term is index: One can write <math>k=\mathbb{ind}_b a \pmod{m}</math> (read "the index of <math>a</math> to the base <math>b</math> modulo <math>m</math>") for <math>b^k \equiv a \pmod{m}</math> if <math>b</math> is a primitive root of <math>m</math> and <math>\gcd(a,m)=1</math>.

Discrete logarithms are quickly computable in a few special cases. However, no efficient method is known for computing them in general. In cryptography, the computational complexity of the discrete logarithm problem, along with its application, was first proposed in the Diffie–Hellman problem. Several important algorithms in public-key cryptography, such as ElGamal, base their security on the hardness assumption that the discrete logarithm problem (DLP) over carefully chosen groups has no efficient solution, and in a general black box group lacks a subexponential solution at all.

Definition

Let <math>G</math> be any group. Denote its group operation by multiplication and its identity element by <math>1</math>. Let <math>b</math> be any element of <math>G</math>. For any positive integer <math>k</math>, the expression <math>b^k</math> denotes the product of <math>b</math> with itself <math>k</math> times:

:<math>b^k = \underbrace{b \cdot b \cdot \ldots \cdot b}_{k \; \text{factors.</math>

Similarly, let <math>b^{-k}</math> denote the product of <math>b^{-1}</math> with itself <math>k</math> times. For <math>k=0</math>, the <math>k</math>th power is the identity: <math>b^0=1</math>.

Let <math>a</math> also be an element of <math>G</math>. An integer <math>k</math> that solves the equation <math>b^k=a</math> is termed a discrete logarithm (or simply logarithm, in this context) of <math>a</math> to the base <math>b</math>. One writes <math>k=\log_b a</math>.

Examples

Powers of 10

The powers of 10 are

:<math>\ldots, 0.001, 0.01, 0.1, 1, 10, 100, 1000, \ldots.</math>

For any number <math>a</math> in this list, one can compute <math>\log_{10}a</math>. For example, <math>\log_{10}{10000}=4</math>, and <math>\log_{10}{0.001}=-3</math>. These are instances of the discrete logarithm problem.

Other base-10 logarithms in the real numbers are not instances of the discrete logarithm problem, because they involve non-integer exponents. For example, the equation <math>\log_{10}{53}=1.724276\ldots</math> means that <math>10^{1.724276\ldots}=53</math>. While integer exponents can be defined in any group using products and inverses, arbitrary real exponents, such as this 1.724276…, require other concepts such as the exponential function.

In group-theoretic terms, the powers of 10 form a cyclic group <math>G</math> under multiplication, and 10 is a generator for this group. The discrete logarithm <math>\log_{10}a</math> is defined for any <math>a</math> in <math>G</math>.

Powers of a fixed real number

A similar example holds for any non-zero real number <math>b</math>. The powers form a multiplicative subgroup <math>G = \{\ldots , b^{-2}, b^{-1}, 1, b^{1}, b^{2}, \ldots \}</math> of the non-zero real numbers. For any element <math>a</math> of <math>G</math>, one can compute <math>\log_b a</math>.

Modular arithmetic

One of the simplest settings for discrete logarithms is the group Zp×. This is the group of multiplication modulo the prime <math>p</math>. Its elements are non-zero congruence classes modulo <math>p</math>, and the group product of two elements may be obtained by ordinary integer multiplication of the elements followed by reduction modulo <math>p</math>.

The <math>k</math>th power of one of the numbers in this group may be computed by finding its '<math>k</math>th power as an integer and then finding the remainder after division by <math>p</math>. When the numbers involved are large, it is more efficient to reduce modulo <math>p</math> multiple times during the computation. Regardless of the specific algorithm used, this operation is called modular exponentiation. For example, consider Z17×. To compute <math>3^4</math> in this group, compute <math>3^4=81</math>, and then divide <math>81</math> by <math>17</math>, obtaining a remainder of <math>13</math>. Thus <math>3^4=13</math> in the group Z17×.

The discrete logarithm is just the inverse operation. For example, consider the equation <math>3^k \equiv 13 \pmod{17}</math>. From the example above, one solution is <math>k=4</math>, but it is not the only solution. Since <math>3^{16}\equiv 1 \pmod{17}</math> —as follows from Fermat's little theorem— it also follows that if <math>n</math> is an integer then <math>3^{4+16n}\equiv 3^4\cdot (3^{16})^n \equiv 3^4 \cdot 1^n \equiv 3^4 \equiv 13 \pmod{17}</math>. Hence the equation has infinitely many solutions of the form <math>4+16n</math>. Moreover, because <math>16</math> is the smallest positive integer <math>m</math> satisfying <math>3^m\equiv 1 \pmod{17}</math>, these are the only solutions. Equivalently, the set of all possible solutions can be expressed by the constraint that <math>k\equiv 4 \pmod{16}</math>.

Powers of the identity

In the special case where <math>b</math> is the identity element <math>1</math> of the group <math>G</math>, the discrete logarithm <math>\log_ba</math> is undefined for <math>a</math> other than <math>1</math>, and every integer <math>k</math> is a discrete logarithm for <math>a=1</math>.

Properties

Powers obey the usual algebraic identity <math>b^{k+l}=b^k\cdot b^l</math>.

Efficient classical algorithms also exist in certain special cases. For example, in the group of the integers modulo <math>p</math> under addition, the power <math>b^k</math> becomes a product <math>b \cdot k</math>, and equality means congruence modulo <math>p</math> in the integers. The extended Euclidean algorithm finds <math>k</math> quickly.

With Diffie–Hellman, a cyclic group modulo a prime <math>p</math> is used, allowing an efficient computation of the discrete logarithm with Pohlig–Hellman if the order of the group (being <math>p-1</math>) is sufficiently smooth, i.e. has no large prime factors.

Comparison with integer factorization

While computing discrete logarithms and integer factorization are distinct problems, they share some properties:

both are special cases of the hidden subgroup problem for finite abelian groups,
both problems seem to be 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 <math>\mathbf{Z}_p^\times</math>) 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 (and other possibly one-way functions) have been exploited in the construction of cryptographic systems.

Popular choices for the group <math>G</math> in discrete logarithm cryptography (DLC) are the cyclic groups <math>\mathbf{Z}_p^\times</math> (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).

While there is no publicly known algorithm for solving the discrete logarithm problem in general, the first three steps of the number field sieve algorithm only depend on the group <math>G</math>, not on the specific elements of <math>G</math> whose finite <math>\log</math> is desired. By precomputing these three steps for a specific group, one need only carry out the last step, which is much less computationally expensive than the first three, to obtain a specific logarithm in that group. The Logjam attack used this vulnerability to compromise a variety of internet services that allowed the use of groups whose order was a 512-bit prime number, so called export grade.