Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Discrete logarithm
Summary
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.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Related publications (39)