Discrete logarithm

In mathematics, for given real numbers a and b, the logarithm logb a is a number x such that bx = a. Analogously, in any group G, powers bk can be defined for all integers k, and the discrete logarithm logb a is an integer k such that bk = a. In number theory, the more commonly used term is index: we can write x = indr a (mod m) (read "the index of a to the base r modulo m") for rx ≡ a (mod m) if r 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. Several important algorithms in public-key cryptography, such as ElGamal, base their security on the assumption that the discrete logarithm problem (DLP) over carefully chosen groups has no efficient solution. 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 bk denotes the product of b with itself k times: Similarly, let b−k denote the product of b−1 with itself k times. For k = 0, the kth power is the identity: b0 = 1. Let a also be an element of G. An integer k that solves the equation bk = a is termed a discrete logarithm (or simply logarithm, in this context) of a to the base b. One writes k = logb a. The powers of 10 are For any number a in this list, one can compute log10 a. For example, log10 10000 = 4, and log10 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 log10 53 = 1.724276... means that 101.724276... = 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.