Editing Discrete logarithm (section)

{{Short description|The problem of inverting exponentiation in groups}}
{{Use dmy dates|date=August 2023|cs1-dates=y}}
In [[mathematics]], for given [[real number]]s <math>a</math> and <math>b</math>, the [[logarithm]] <math>\log_b(a)</math> is a number <math>x</math> such that <math>b^x=a</math>. Analogously, in any [[group (mathematics)|group]] <math>G</math>, powers <math>b^k</math> can be defined for all [[integer]]s <math>k</math>, and the '''discrete logarithm''' <math>\log_b(a)</math> is an integer <math>k</math> such that <math>b^k=a</math>. In [[modular arithmetic|arithmetic modulo]] an integer <math>m</math>, the more commonly used term is '''index''': One can write <math>k=\mathbb{ind}_b a \pmod{m}</math> (read "the index of <math>a</math> to the base <math>b</math> modulo <math>m</math>") for <math>b^k \equiv a \pmod{m}</math> if <math>b</math> is a [[primitive root modulo n|primitive root]] of <math>m</math> and <math>\gcd(a,m)=1</math>.

Discrete logarithms are quickly computable in a few special cases. However, no efficient method is known for computing them in general. In cryptography, the computational complexity of the discrete logarithm problem, along with its application, was first proposed in the [[Diffie–Hellman problem]]. Several important [[algorithm]]s in [[public-key cryptography]], such as [[ElGamal cryptosystem|ElGamal]], base their security on the [[computational hardness assumption|hardness assumption]] that the discrete logarithm problem (DLP) over carefully chosen groups has no efficient solution.<ref>{{Cite book |author-first1=A. J. |author-last1=Menezes |title=Handbook of Applied Cryptography |author-first2=P. C. |author-last2=van Oorschot |author-first3=S. A. |author-last3=Vanstone |publisher=[[CRC Press]] |chapter=Chapter 8.4 ElGamal public-key encryption |chapter-url=https://cacr.uwaterloo.ca/hac/about/chap8.pdf}}</ref>