View source for Discrete logarithm

{{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 ''a'' and ''b'', the [[logarithm]] log<sub>''b''</sub>&thinsp;''a'' is a number ''x'' such that {{nowrap|1=''b''<sup>''x''</sup> = ''a''}}. Analogously, in any [[group (mathematics)|group]] ''G'', powers ''b''<sup>''k''</sup> can be defined for all [[integer]]s ''k'', and the '''discrete logarithm''' log<sub>''b''</sub>&thinsp;''a'' is an integer ''k'' such that {{nowrap|1=''b''<sup>''k''</sup> = ''a''}}. In [[modular arithmetic|arithmetic modulo]] an integer ''m'', the more commonly used term is '''index''': One can write ''k'' = ind<sub>''b''</sub> ''a'' (mod&nbsp;''m'') (read "the index of ''a'' to the base ''b'' modulo ''m''") for ''b''<sup>&thinsp;''k''</sup> ≡ ''a'' (mod&nbsp;''m'') if ''b'' is a [[primitive root modulo n|primitive root]] of ''m'' and [[Greatest common divisor|gcd]](''a'',''m'')&nbsp;=&nbsp;1.

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>

== Definition ==
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 ''b''<sup>''k''</sup> denotes the product of ''b'' with itself ''k'' times:<ref name=":0">{{Cite book |author-last1=Lam |url=https://link.springer.com/book/10.1007/978-3-0348-8295-8 |title=Cryptography and Computational Number Theory |author-last2=Shparlinski |author-last3=Wang |author-last4=Xing |editor-first1=Kwok-Yan |editor-first2=Igor |editor-first3=Huaxiong |editor-first4=Chaoping |editor-last1=Lam |editor-last2=Shparlinski |editor-last3=Wang |editor-last4=Xing |publisher=[[Birkhäuser Basel]] |isbn=978-3-7643-6510-3 |edition=1 |series=Progress in Computer Science and Applied Logic |date=2001 |pages=54–56 |language=en |doi=10.1007/978-3-0348-8295-8 |eissn=2297-0584 |issn=2297-0576}}</ref>
:<math>b^k = \underbrace{b \cdot b \cdot \ldots \cdot b}_{k \; \text{factors}}.</math>
Similarly, let ''b''<sup>−''k''</sup> denote the product of ''b''<sup>−1</sup> with itself ''k'' times. For ''k'' = 0, the ''k''th power is the identity: {{nowrap|1=''b''<sup>0</sup> = 1}}.

Let ''a'' also be an element of ''G''. An integer ''k'' that solves the equation {{nowrap|1=''b''<sup>''k''</sup> = ''a''}} is termed a '''discrete logarithm''' (or simply '''logarithm''', in this context) of ''a'' to the base ''b''. One writes ''k''&nbsp;=&nbsp;log<sub>''b''</sub>&thinsp;''a''.

==Examples==
=== Powers of 10 ===
The [[power of 10|powers of 10]] are
:<math>\ldots, 0.001, 0.01, 0.1, 1, 10, 100, 1000, \ldots.</math>
For any number ''a'' in this list, one can compute log<sub>10</sub>&thinsp;''a''. For example, log<sub>10</sub>&thinsp;10000 = 4, and log<sub>10</sub>&thinsp;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 log<sub>10</sub>&thinsp;53 = 1.724276… means that 10<sup>1.724276…</sup> = 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 [[cyclic group|generator]] for this group. The discrete logarithm log<sub>10</sub>&thinsp;''a'' is defined for any ''a'' in ''G''.

=== Powers of a fixed real number ===
A similar example holds for any non-zero real number ''b''. The powers form a multiplicative [[subgroup]] ''G'' = {…, ''b''<sup>−3</sup>, ''b''<sup>−2</sup>, ''b''<sup>−1</sup>, 1, ''b''<sup>1</sup>, ''b''<sup>2</sup>, ''b''<sup>3</sup>, …} of the non-zero real numbers. For any element ''a'' of ''G'', one can compute log<sub>''b''</sub>&thinsp;''a''.

=== Modular arithmetic ===
One of the simplest settings for discrete logarithms is the group [[multiplicative group of integers modulo n|'''Z'''<sub>''p''</sub><sup>×</sup>]]. This is the group of multiplication [[modular arithmetic|modulo]] the [[prime number|prime]] ''p''. Its elements are non-zero [[Modular arithmetic#Congruence class|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&nbsp;''p''.

The ''k''th [[exponentiation|power]] of one of the numbers in this group may be computed by finding its ''k''th power as an integer and then finding the remainder after division by ''p''. When the numbers involved are large, it is more efficient to reduce modulo ''p'' multiple times during the computation. Regardless of the specific algorithm used, this operation is called [[modular exponentiation]]. For example, consider '''Z'''<sub>17</sub><sup>×</sup>. To compute 3<sup>4</sup> in this group, compute 3<sup>4</sup> = 81, and then divide 81 by 17, obtaining a remainder of 13. Thus 3<sup>4</sup> = 13 in the group '''Z'''<sub>17</sub><sup>×</sup>.

The discrete logarithm is just the inverse operation. For example, consider the equation 3<sup>''k''</sup> ≡ 13 (mod 17). From the example above, one solution is ''k''&nbsp;=&nbsp;4, but it is not the only solution. Since 3<sup>16</sup> ≡ 1 (mod 17)—as follows from [[Fermat's little theorem]]—it also follows that if ''n'' is an integer then 3<sup>4+16''n''</sup> ≡ 3<sup>4</sup> × (3<sup>16</sup>)<sup>''n''</sup> ≡ 13 × 1<sup>''n''</sup> ≡ 13 (mod 17). Hence the equation has infinitely many solutions of the form 4 + 16''n''. Moreover, because 16 is the smallest positive integer ''m'' satisfying 3<sup>''m''</sup> ≡ 1 (mod 17), these are the only solutions. Equivalently, the set of all possible solutions can be expressed by the constraint that ''k'' ≡ 4 (mod 16).

=== Powers of the identity ===
In the special case where ''b'' is the identity element 1 of the group ''G'', the discrete logarithm log<sub>''b''</sub>&thinsp;''a'' is undefined for ''a'' other than 1, and every integer ''k'' is a discrete logarithm for ''a'' = 1.

== Properties ==
Powers obey the usual algebraic identity ''b''<sup>''k''&thinsp;+&thinsp;''l''</sup> = ''b''<sup>''k''</sup>&thinsp;''b''<sup>&hairsp;''l''</sup>.<ref name=":0" /> In other words, the [[function (mathematics)|function]]
:<math>f \colon \mathbf{Z} \to G</math>
defined by ''f''(''k'') = ''b''<sup>''k''</sup> is a [[group homomorphism]] from the integers '''Z''' under addition [[Surjection|onto]] the [[subgroup]] ''H'' of ''G'' [[generating set of a group|generated]] by ''b''. For all ''a'' in ''H'', log<sub>''b''</sub>&thinsp;''a'' exists. [[Converse (logic)|Converse]]ly, log<sub>''b''</sub>&thinsp;''a'' does not exist for ''a'' that are not in ''H''.

If ''H'' is [[infinite group|infinite]], then log<sub>''b''</sub>&thinsp;''a'' is also unique, and the discrete logarithm amounts to a [[group isomorphism]]

:<math>\log_b \colon H \to \mathbf{Z}.</math>

On the other hand, if ''H'' is [[finite group|finite]] of [[order of a group|order]] ''n'', then log<sub>''b''</sub>&thinsp;''a'' is unique only up to [[modular arithmetic|congruence modulo ''n'']], and the discrete logarithm amounts to a group isomorphism
:<math>\log_b\colon H \to \mathbf{Z}_n,</math>
where '''Z'''<sub>''n''</sub> denotes the additive group of integers modulo ''n''.

The familiar base change formula for ordinary logarithms remains valid: If ''c'' is another generator of ''H'', then

:<math>\log_c a = \log_c b \cdot \log_b a.</math>

== Algorithms ==
{{See also|Discrete logarithm records}}
{{unsolved|computer science|Can the discrete logarithm be computed in polynomial time on a classical computer?}}
The discrete logarithm problem is considered to be computationally intractable. That is, no efficient classical algorithm is known for computing discrete logarithms in general.

A general algorithm for computing log<sub>''b''</sub>&thinsp;''a'' in finite groups ''G'' is to raise ''b'' to larger and larger powers ''k'' until the desired ''a'' is found. This algorithm is sometimes called ''trial multiplication''. It requires [[running time]] [[linear time|linear]] in the size of the group ''G'' and thus [[exponential time|exponential]] in the number of digits in the size of the group. Therefore, it is an exponential-time algorithm, practical only for small groups ''G''.

More sophisticated algorithms exist, usually inspired by similar algorithms for [[integer factorization]]. These algorithms run faster than the naïve algorithm, some of them proportional to the [[square root]] of the size of the group, and thus exponential in half the number of digits in the size of the group. However, none of them runs in [[polynomial time]] (in the number of digits in the size of the group).

* [[Baby-step giant-step]]
* [[Function field sieve]]
* [[Index calculus algorithm]]
* [[General number field sieve|Number field sieve]]
* [[Pohlig–Hellman algorithm]]
* [[Pollard's rho algorithm for logarithms]]
* [[Pollard's kangaroo algorithm]] (aka Pollard's lambda algorithm)

There is an efficient [[Shor's algorithm|quantum algorithm]] due to [[Peter Shor]].<ref>{{cite journal |arxiv=quant-ph/9508027 |title=Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer |author-first=Peter |author-last=Shor |journal=SIAM Journal on Computing |volume=26 |issue=5 |date=1997 |pages=1484–1509 |doi=10.1137/s0097539795293172 |mr=1471990 |s2cid=2337707}}</ref>

Efficient classical algorithms also exist in certain special cases. For example, in the group of the integers modulo ''p'' under addition, the power ''b''<sup>''k''</sup> becomes a product ''bk'', and equality means congruence modulo ''p'' in the integers. The [[extended Euclidean algorithm]] finds ''k'' quickly.

With [[Diffie–Hellman_key_exchange|Diffie–Hellman]], a cyclic group modulo a prime ''p'' is used, allowing an efficient computation of the discrete logarithm with Pohlig–Hellman if the order of the group (being ''p''−1) is sufficiently [[smooth number|smooth]], i.e. has no large [[prime factor]]s.

== Comparison with integer factorization ==
While computing discrete logarithms and integer factorization are distinct problems, they share some properties:
* both are special cases of the [[hidden subgroup problem]] for [[finite abelian group]]s,
* both problems seem to be difficult (no efficient algorithms are known for non-[[quantum computer]]s),
* for both problems efficient algorithms on quantum computers are known,
* algorithms from one problem are often adapted to the other, and
* the difficulty of both problems has been used to construct various [[cryptographic]] systems.

== Cryptography ==
There exist groups for which computing discrete logarithms is apparently difficult.  In some cases (e.g. large prime order subgroups of  groups '''Z'''<sub>''p''</sub><sup>×</sup>) there is not only no efficient algorithm known for the worst case, but the [[average-case complexity]] can be shown to be about as hard as the worst case using [[random self-reducibility]].<ref>{{Cite journal |author-last1=Blake |author-first1=Ian F. |author-last2=Garefalakis |author-first2=Theo |date=2004-04-01 |title=On the complexity of the discrete logarithm and Diffie–Hellman problems |journal=Journal of Complexity |series=Festschrift for Harald Niederreiter, Special Issue on Coding and Cryptography |language=en |volume=20 |issue=2 |pages=148–170 |doi=10.1016/j.jco.2004.01.002 |issn=0885-064X |doi-access=free}}</ref>

At the same time, the inverse problem of discrete exponentiation is not difficult (it can be computed efficiently using [[exponentiation by squaring]], for example).  This asymmetry is analogous to the one between integer factorization and integer multiplication. Both asymmetries (and other possibly [[one-way function]]s) have been exploited in the construction of cryptographic systems.

Popular choices for the group ''G'' in discrete logarithm cryptography (DLC) are the cyclic groups '''Z'''<sub>''p''</sub><sup>×</sup> (e.g. [[ElGamal encryption]], [[Diffie–Hellman key exchange]], and the [[Digital Signature Algorithm]]) and cyclic subgroups of [[elliptic curve]]s over [[finite field]]s (''see'' [[Elliptic curve cryptography]]).

While there is no publicly known algorithm for solving the discrete logarithm problem in general, the first three steps of the [[General number field sieve|number field sieve]] algorithm only depend on the group ''G'', not on the specific elements of ''G'' whose finite log is desired. By [[precomputing]] these three steps for a specific group, one need only carry out the last step, which is much less computationally expensive than the first three, to obtain a specific logarithm in that group.<ref name=imperfectfs/>

It turns out that much [[internet]] traffic uses one of a handful of groups that are of order 1024 bits or less, e.g. cyclic groups with order of the Oakley primes specified in <nowiki>RFC 2409</nowiki>.<ref>{{Cite journal |author-last1=Harkins |author-first1=D. |author-last2=Carrel |author-first2=D. |date=November 1998 |title=The Internet Key Exchange (IKE) |url=https://www.rfc-editor.org/rfc/rfc2409 |journal=Network Working Group |language=en |doi=10.17487/RFC2409 |issn=2070-1721}}</ref> The [[Logjam (computer security)|Logjam]] attack used this vulnerability to compromise a variety of internet services that allowed the use of groups whose order was a 512-bit prime number, so called [[export of cryptography|export grade]].<ref name=imperfectfs/>

The authors of the Logjam attack estimate that the much more difficult precomputation needed to solve the discrete log problem for a 1024-bit prime would be within the budget of a large national [[intelligence agency]] such as the U.S. [[National Security Agency]] (NSA). The Logjam authors speculate that precomputation against widely reused 1024 DH primes is behind claims in [[Global surveillance disclosures (2013–present)|leaked NSA documents]] that NSA is able to break much of current cryptography.<ref name=imperfectfs>{{cite web |author-last1=Adrian |author-first1=David |author-last2=Bhargavan |author-first2=Karthikeyan |author-last3=Durumeric |author-first3=Zakir |author-last4=Gaudry |author-first4=Pierrick |author-last5=Green |author-first5=Matthew |author-last6=Halderman |author-first6=J. Alex |author-last7=Heninger |author-first7=Nadia |author-link7=Nadia Heninger |author-last8=Springall |author-first8=Drew |author-last9=Thomé |author-first9=Emmanuel |author-last10=Valenta |author-first10=Luke |author-last11=VanderSloot |author-first11=Benjamin |author-last12=Wustrow |author-first12=Eric |author-last13=Zanella-Béguelin |author-first13=Santiago |author-last14=Zimmermann |author-first14=Paul |title=Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice |url=https://weakdh.org/imperfect-forward-secrecy.pdf |date=October 2015}}</ref>

== See also ==
* [[A. W. Faber Model 366]]
* [[Percy Ludgate]] and [[Irish logarithm]]

== References ==
{{Reflist}}
{{Refbegin}}
* {{cite book |author-last1=Rosen |author-first1=Kenneth H. |title=Elementary Number Theory and Its Application |date=2011 |publisher=Pearson |isbn=978-0321500311 |page=368 |edition=6}}
* {{cite web |author-last=Weisstein |author-first=Eric W. |title=Discrete Logarithm |url=http://mathworld.wolfram.com/DiscreteLogarithm.html |website=MathWorld |publisher=Wolfram Web |access-date=1 January 2019}}
{{Refend}}

== Further reading ==
* [[Richard Crandall]]; [[Carl Pomerance]]. Chapter 5, ''Prime Numbers: A computational perspective'', 2nd ed., Springer.
* {{Cite book |author-last1=Stinson |author-first1=Douglas Robert |title=Cryptography: Theory and Practice |publisher=[[CRC Press]] |location=London, UK |edition=3 |isbn=978-1-58488-508-5 |date=2006}}

{{Number theoretic algorithms}}
{{Cryptography public-key}}
{{Computational hardness assumptions}}

{{DEFAULTSORT:Discrete Logarithm}}
[[Category:Modular arithmetic]]
[[Category:Group theory]]
[[Category:Cryptography]]
[[Category:Logarithms]]
[[Category:Finite fields]]
[[Category:Computational hardness assumptions]]
[[Category:Unsolved problems in computer science]]