Discrete logarithm

In mathematics, for given real numbers a {\displaystyle a} and b {\displaystyle b} , the logarithm log b ⁡ ( a ) {\displaystyle \log _{b}(a)} is a number x {\displaystyle x} such that b x = a {\displaystyle b^{x}=a} . The discrete logarithm is an analogous concept in group theory. In any group G {\displaystyle G} , powers b k {\displaystyle b^{k}} can be defined for all integers k {\displaystyle k} , and the discrete logarithm log b ⁡ ( a ) {\displaystyle \log _{b}(a)} is an integer k {\displaystyle k} such that b k = a {\displaystyle b^{k}=a} . In the special case of arithmetic modulo an integer m {\displaystyle m} , the more commonly used term is index: One can write k = ind b ⁡ a ( mod m ) {\displaystyle k=\operatorname {ind} _{b}a\!\!\!\!{\pmod {m}}} when b k ≡ a ( mod m ) {\displaystyle 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.