Discrete logarithm

In the mathematics of the real numbers, the logarithm logb a is a number x such that bx = a, for given numbers a and b. 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. In the mathematics of the real numbers, the logarithm logb a is a number x such that bx = a, for given numbers a and b. 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 base their security on the assumption that the discrete logarithm problem 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 form an infinite subset G = {…, 0.001, 0.01, 0.1, 1, 10, 100, 1000, …} of the rational numbers. This set G is a cyclic group under multiplication, and 10 is a generator. For any element a of the group, 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 in the real numbers require other concepts such as the exponential function. A similar example holds for any non-zero real number b. The powers form a multiplicative subgroup G = {…, b−3, b−2, b−1, 1, b1, b2, b3, …} of the non-zero real numbers. For any element a of G, one can compute logb a. One of the simplest settings for discrete logarithms is the group (Zp)×. This is the group of multiplication modulo the prime p. Its elements are 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.