HOME

TheInfoList



OR:

In
mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
, for given
real number In mathematics, a real number is a number that can be used to measure a continuous one- dimensional quantity such as a duration or temperature. Here, ''continuous'' means that pairs of values can have arbitrarily small differences. Every re ...
s a and b, the
logarithm In mathematics, the logarithm of a number is the exponent by which another fixed value, the base, must be raised to produce that number. For example, the logarithm of to base is , because is to the rd power: . More generally, if , the ...
\log_b(a) is a number x such that b^x=a. Analogously, in any group G, powers b^k can be defined for all
integer An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...
s k, and the discrete logarithm \log_b(a) is an integer k such that b^k=a. In arithmetic modulo an integer m, the more commonly used term is index: One can write k=\mathbb_b a \pmod (read "the index of a to the base b modulo m") for b^k \equiv a \pmod if b is a primitive root of m and \gcd(a,m)=1. 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
algorithm In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
s in
public-key cryptography Public-key cryptography, or asymmetric cryptography, is the field of cryptographic systems that use pairs of related keys. Each key pair consists of a public key and a corresponding private key. Key pairs are generated with cryptographic alg ...
, such as ElGamal, base their security on the hardness assumption that the discrete logarithm problem (DLP) over carefully chosen groups has no efficient solution.


Definition

Let G be any group. Denote its group operation by multiplication and its
identity element In mathematics, an identity element or neutral element of a binary operation is an element that leaves unchanged every element when the operation is applied. For example, 0 is an identity element of the addition of real numbers. This concept is use ...
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: :b^k = \underbrace_. Similarly, let b^ denote the product of b^ with itself k times. For k=0, the kth power is the identity: b^0=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.


Examples


Powers of 10

The powers of 10 are :\ldots, 0.001, 0.01, 0.1, 1, 10, 100, 1000, \ldots. For any number a in this list, one can compute \log_a. For example, \log_=4, and \log_=-3. 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 \log_=1.724276\ldots means that 10^. 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 In abstract algebra, a cyclic group or monogenous group is a Group (mathematics), group, denoted C_n (also frequently \Z_n or Z_n, not to be confused with the commutative ring of P-adic number, -adic numbers), that is Generating set of a group, ge ...
G under multiplication, and 10 is a generator for this group. The discrete logarithm \log_a is defined for any a in G.


Powers of a fixed real number

A similar example holds for any non-zero real number b. The powers form a multiplicative
subgroup In group theory, a branch of mathematics, a subset of a group G is a subgroup of G if the members of that subset form a group with respect to the group operation in G. Formally, given a group (mathematics), group under a binary operation  ...
G = \ of the non-zero real numbers. For any element a of G, one can compute \log_b a.


Modular arithmetic

One of the simplest settings for discrete logarithms is the group Z''p''×. This is the group of multiplication
modulo In computing and mathematics, the modulo operation returns the remainder or signed remainder of a division, after one number is divided by another, the latter being called the '' modulus'' of the operation. Given two positive numbers and , mo ...
the
prime A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
p. Its elements are non-zero 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. When the numbers involved are large, it is more efficient to reduce modulo p multiple times during the computation. Regardless of the specific algorithm used, this operation is called modular exponentiation. For example, consider Z17×. To compute 3^4 in this group, compute 3^4=81, and then divide 81 by 17, obtaining a remainder of 13. Thus 3^4=13 in the group Z17×. The discrete logarithm is just the inverse operation. For example, consider the equation 3^k \equiv 13 \pmod. From the example above, one solution is k=4, but it is not the only solution. Since 3^\equiv 1 \pmod —as follows from
Fermat's little theorem In number theory, Fermat's little theorem states that if is a prime number, then for any integer , the number is an integer multiple of . In the notation of modular arithmetic, this is expressed as a^p \equiv a \pmod p. For example, if and , t ...
— it also follows that if n is an integer then 3^\equiv 3^4\cdot (3^)^n \equiv 3^4 \cdot 1^n \equiv 3^4 \equiv 13 \pmod. Hence the equation has infinitely many solutions of the form 4+16n. Moreover, because 16 is the smallest positive integer m satisfying 3^m\equiv 1 \pmod, these are the only solutions. Equivalently, the set of all possible solutions can be expressed by the constraint that k\equiv 4 \pmod.


Powers of the identity

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


Properties

Powers obey the usual algebraic identity b^=b^k\cdot b^l. In other words, the function :f \colon \mathbf \to G defined by f(k)=b^k is a
group homomorphism In mathematics, given two groups, (''G'',∗) and (''H'', ·), a group homomorphism from (''G'',∗) to (''H'', ·) is a function ''h'' : ''G'' → ''H'' such that for all ''u'' and ''v'' in ''G'' it holds that : h(u*v) = h(u) \cdot h(v) whe ...
from the group of integers \mathbf under addition
onto In mathematics, a surjective function (also known as surjection, or onto function ) is a function such that, for every element of the function's codomain, there exists one element in the function's domain such that . In other words, for a f ...
the
subgroup In group theory, a branch of mathematics, a subset of a group G is a subgroup of G if the members of that subset form a group with respect to the group operation in G. Formally, given a group (mathematics), group under a binary operation  ...
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 In abstract algebra, a group isomorphism is a function between two groups that sets up a bijection between the elements of the groups in a way that respects the given group operations. If there exists an isomorphism between two groups, then the ...
:\log_b \colon H \to \mathbf. On the other hand, if H is finite of order n, then \log_b a is 0 unique only up to congruence modulo n, and the discrete logarithm amounts to a group isomorphism :\log_b\colon H \to \mathbf_n, where \mathbf_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 :\log_c a = \log_c b \cdot \log_b a.


Algorithms

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 mathematics, the term ''linear'' is used in two distinct senses for two different properties: * linearity of a '' function'' (or '' mapping''); * linearity of a '' polynomial''. An example of a linear function is the function defined by f(x) ...
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 In mathematics, integer factorization is the decomposition of a positive integer into a product of integers. Every positive integer greater than 1 is either the product of two or more integer factors greater than 1, in which case it is a comp ...
. These algorithms run faster than the naïve algorithm, some of them proportional to the
square root In mathematics, a square root of a number is a number such that y^2 = x; in other words, a number whose ''square'' (the result of multiplying the number by itself, or y \cdot y) is . For example, 4 and −4 are square roots of 16 because 4 ...
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 In quantum computing, a quantum algorithm is an algorithm that runs on a realistic model of quantum computation, the most commonly used model being the quantum circuit model of computation. A classical (or non-quantum) algorithm is a finite seq ...
due to Peter Shor. 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 b \cdot k, and equality means congruence modulo p in the integers. The
extended Euclidean algorithm In arithmetic and computer programming, the extended Euclidean algorithm is an extension to the Euclidean algorithm, and computes, in addition to the greatest common divisor (gcd) of integers ''a'' and ''b'', also the coefficients of Bézout's id ...
finds k quickly. With Diffie–Hellman, a cyclic group modulo 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 factor A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
s.


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 Cryptography, or cryptology (from "hidden, secret"; and ''graphein'', "to write", or '' -logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adversarial behavior. More gen ...
systems.


Cryptography

There exist groups for which computing discrete logarithms is apparently difficult. In some cases (e.g. large prime order subgroups of groups \mathbf_p^\times) 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 function In computer science, a one-way function is a function that is easy to compute on every input, but hard to invert given the image of a random input. Here, "easy" and "hard" are to be understood in the sense of computational complexity theory, s ...
s) have been exploited in the construction of cryptographic systems. Popular choices for the group G in discrete logarithm cryptography (DLC) are the cyclic groups \mathbf_p^\times (e.g. ElGamal encryption, Diffie–Hellman key exchange, and the
Digital Signature Algorithm The Digital Signature Algorithm (DSA) is a Public-key cryptography, public-key cryptosystem and Federal Information Processing Standards, Federal Information Processing Standard for digital signatures, based on the mathematical concept of modular e ...
) and cyclic subgroups of elliptic curves over
finite field In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field (mathematics), field that contains a finite number of Element (mathematics), elements. As with any field, a finite field is a Set (mathematics), s ...
s (''see''
Elliptic curve cryptography Elliptic-curve cryptography (ECC) is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. ECC allows smaller keys to provide equivalent security, compared to cryptosystems based on modula ...
). 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. It turns out that much
internet The Internet (or internet) is the Global network, global system of interconnected computer networks that uses the Internet protocol suite (TCP/IP) to communicate between networks and devices. It is a internetworking, network of networks ...
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. 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. 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 An intelligence agency is a government agency responsible for the collection, Intelligence analysis, analysis, and exploitation of information in support of law enforcement, national security, military, public safety, and foreign policy obj ...
such as the U.S.
National Security Agency The National Security Agency (NSA) is an intelligence agency of the United States Department of Defense, under the authority of the director of national intelligence (DNI). The NSA is responsible for global monitoring, collection, and proces ...
(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.


See also

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


References

* *


Further reading

* Richard Crandall; Carl Pomerance. Chapter 5, ''Prime Numbers: A computational perspective'', 2nd ed., Springer. * {{DEFAULTSORT:Discrete Logarithm Modular arithmetic Group theory Cryptography Logarithms Finite fields Computational hardness assumptions Unsolved problems in computer science