## Discrete logarithm

### Introduction

In mathematics, for given real numbers a and b, the logarithm logb a maybe a number x such bx = a. analogously, in any group G, powers bk are often defined for all integers k, and therefore the discrete logarithm logb a is an integer k such bk = a. In number theory, the more commonly used term is index: we will write x = indr a (mod m) (read “the index of a to the bottom r modulo m”) for rx ≡ a (mod m) if r may be a primitive root of m and gcd(a,m) = 1.

Discrete logarithms are quickly computable during a few special cases. However, no efficient method is understood for computing them generally. Several important algorithms in public-key cryptography base their security on the idea that the discrete logarithm problem over carefully chosen groups has no efficient solution.

### Definition

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

{displaystyle b^{k}=underbrace {bcdot bcdots b} _{k;{text{factors}}}.}{displaystyle b^{k}=underbrace {bcdot bcdots b} _{k;{text{factors}}}.}

Similarly, let b−k denote the merchandise of b−1 with itself k times. For k = 0, the kth power is that the identity: b0 = 1.

Let an even be a component of G. An integer k that solves the equation bk = a is termed a discrete logarithm (or simply logarithm, during this context) of a to the bottom b. One writes k = logb a.

### Algorithms

The discrete logarithm problem is taken into account to be computationally intractable. That is, no efficient classical algorithm is understood for computing discrete logarithms generally.

A general algorithm for computing logb an infinite groups G is to boost b to larger and bigger powers k until the specified is found. This algorithm is usually called trial multiplication. It requires a time period linear within the size of the group G and thus exponential within the number of digits within the size of the group. So, it’s an exponential-time algorithm, practical just 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, a number of them proportional to the root of the dimensions of the group, and thus exponential in half the amount of digits within the size of the group. However, none of them run in polynomial time (in the number of digits within 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 thanks to Peter Shor. Efficient classical algorithms also exist in certain special cases. For instance, within the group of the integers modulo p under addition, the facility bk becomes a product bk, and equality means congruence modulo p within the integers. The extended Euclidean algorithm finds k quickly.

With Diffie–Hellman a cyclic group modulus a major p is employed, 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.

### Cryptography

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

At an equivalent time, the inverse problem of discrete exponentiation isn’t difficult (it is often 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) are exploited within the construction of cryptographic systems.

Popular choices for the group G in discrete logarithm cryptography (DLC) are the cyclic groups (Zp)× (e.g. ElGamal encryption, Diffie–Hellman key exchange, and therefore the Digital Signature Algorithm) and cyclic subgroups of elliptic curves over finite fields (see Elliptic curve cryptography).

While there’s no publicly known algorithm for solving the discrete logarithm problem generally, the primary three steps of the amount field sieve algorithm only depend upon the group G, not on the precise elements of G whose finite log is desired. By pre-computing these three steps for a selected group, one need only perform the last step, which is far less computationally expensive than the primary three, to get a selected logarithm therein group.

It seems that much Internet traffic uses one among a couple of groups that are of order 1024 bits or less, e.g. cyclic groups with an order of the Oakley primes laid out in RFC 2409. The Logjam attack used this vulnerability to compromise a spread of Internet services that allowed the utilization of groups whose order was a 512-bit prime, so-called export grade.

The authors of the Logjam attack estimate that the far more difficult pre-computation needed to unravel the discrete log problem for a 1024-bit prime would be within the budget of an outsized national intelligence like the U.S. National Security Agency (NSA). The Logjam authors speculate that pre-computation against widely reused 1024 DH primes is behind claims in leaked NSA documents that NSA is in a position to interrupt much of current cryptography.