Discrete logarithm

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

${\displaystyle b^{k}=\underbrace {b\cdot b\cdots b} _{k\;{\text{factors}}}.}$

Similarly, let b^−k denote the product of b⁻¹ with itself k times. For k = 0, the kth power is the identity: b⁰ = 1.

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

Powers obey the usual algebraic identity b^k + l = b^k b^l.[2] In other words, the function

${\displaystyle f\colon \mathbf {Z} \to G}$

defined by f(k) = b^k is a group homomorphism from the integers Z under addition onto the subgroup H of G generated by b. For all a in H, log_b a exists. Conversely, log_b a does not exist for a that are not in H.

If H is infinite, then log_b a is also unique, and the discrete logarithm amounts to a group isomorphism

${\displaystyle \log _{b}\colon H\to \mathbf {Z} .}$

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

${\displaystyle \log _{b}\colon H\to \mathbf {Z} _{n},}$

where Z_n denotes the additive group of integers modulo n.

The familiar base change formula for ordinary logarithms remains valid: If c is another generator of H, then

${\displaystyle \log _{c}a=\log _{c}b\cdot \log _{b}a.}$

The discrete logarithm problem is considered to be computationally intractable. That is, no efficient classical algorithm is known for computing discrete logarithms in general.

A general algorithm for computing log_b a in finite groups G is to raise b to larger and larger powers k until the desired a is found. This algorithm is sometimes called trial multiplication. It 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. Therefore, it is an exponential-time algorithm, practical only for small groups G.

More sophisticated algorithms exist, usually inspired by similar algorithms for integer factorization. These algorithms run faster than the naïve algorithm, some of them proportional to 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).

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

There is an efficient quantum algorithm due to Peter Shor.[3]

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

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

While computing discrete logarithms and factoring integers 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.

There exist groups for which computing discrete logarithms is apparently difficult. In some cases (e.g. large prime order subgroups of groups (Z_p)^×) 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.[4]

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 G in discrete logarithm cryptography (DLC) are the cyclic groups (Z_p)^× (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 G, not on the specific elements of G whose finite log 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.[5]

It turns out that much Internet traffic uses one of a handful of groups that are of order 1024 bits or less, e.g. cyclic groups with order of the Oakley primes specified in RFC 2409.[6] 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.[5]

The authors of the Logjam attack estimate that the much more difficult precomputation needed to solve the discrete log problem for a 1024-bit prime would be within the budget of a large national intelligence agency such as the U.S. National Security Agency (NSA). The Logjam authors speculate that precomputation against widely reused 1024 DH primes is behind claims in leaked NSA documents that NSA is able to break much of current cryptography.[5]

• A. W. Faber Model 366
• Percy Ludgate and Irish logarithm

• Richard Crandall; Carl Pomerance. Chapter 5, Prime Numbers: A computational perspective, 2nd ed., Springer.
• Stinson, Douglas Robert (2006). Cryptography: Theory and Practice (3 ed.). London, UK: CRC Press. ISBN 978-1-58488-508-5.