Discrete logarithm
In mathematics, for given real numbers a and b , the logarithm \log_b(a) is a number x such that b^x = a .
≈ 6 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In mathematics, for given real numbers a and b , the logarithm \log_b(a) is a number x such that b^x = a . The discrete logarithm is an analogous concept in group theory. In any group G , powers b^k can be defined for all integers k , and the discrete logarithm \log_b(a) is an integer k such that b^k = a . In the special case of arithmetic modulo an integer m , the more commonly used term is index: One can write k = \operatorname{ind}_b a \!\!\!\! \pmod{m} when b^k \equiv a \!\!\!\! \pmod{m} .
Discrete logarithms are quickly computable in a few special cases, but no efficient method is known for computing them in general. Several cryptographic systems, including Diffie–Hellman and ElGamal, base their security on the hardness assumption that the discrete logarithm problem over carefully chosen groups has no efficient solution.
In general, there is no subexponential time solution for black box groups. b^k = \underbrace{b \cdot b \cdot \ldots \cdot b}_{k \; \text{factors}}. Similarly, let b^{-k} denote the product of b^{-1} with itself k times. For k=0 , the k th 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
\ldots, 0.001, 0.01, 0.1, 1, 10, 100, 1000, \ldots. For any number a in this list, one can compute \log_{10}a . For example, \log_{10}{10000}=4 , and \log_{10}{0.001}=-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_{10}{53}=1.724276\ldots means that 10^{1.724276\ldots}=53 .
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 G under multiplication, and 10 is a generator for this group.
The discrete logarithm \log_{10}a is defined for any a in G . A similar example holds for any non-zero real number b . The powers form a multiplicative subgroup G = \{\ldots , b^{-2}, b^{-1}, 1, b^{1}, b^{2}, \ldots \} of the non-zero real numbers. For any element a of G , one can compute \log_b a . The k th power of one of the numbers in this group may be computed by finding its k th 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 . 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 . The discrete logarithm is just the inverse operation. For example, consider the equation 3^k \equiv 13 \pmod{17}.
From the example above, one solution is k=4 , and therefore \log_3 13 = 4 in . However, 4 is not the only solution. Because 3^{16}\equiv 1 \pmod{17}, it follows that if n is any integer then 3^{4+16n}\equiv 3^4\cdot (3^{16})^n \equiv 3^4 \cdot 1^n \equiv 3^4 \equiv 13 \pmod{17}.
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{17} , these are the only solutions. Equivalently, the set of all possible solutions can be expressed by the constraint that k \equiv 4 \pmod{16} .
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 . P + Q = (P \; \# \; Q) \; \# \; O. This addition operation makes a commutative group with identity element . For any point of , let k P = P + P + \cdots + P denote the sum of copies of .
In this context, the discrete logarithm problem is: Given points and , find such that Q = k P . When the underlying field is a finite field, this problem has cryptographic applications. Powers obey the usual algebraic identity b^{k+l}=b^k\cdot b^l . In other words, the function f \colon \mathbf{Z} \to G defined by f(k)=b^k is a group homomorphism from the group of integers \mathbf{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 \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 \log_b\colon H \to \mathbf{Z}_n, where \mathbf{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 \log_c a = \log_c b \cdot \log_b a.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1374186946 under CC BY-SA 4.0; modifications have been made.