Editing Discrete logarithm (section)

== 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 <math>\log_b a</math> in finite groups <math>G</math> is to raise <math>b</math> to larger and larger powers <math>k</math> until the desired <math>a</math> is found. This algorithm is sometimes called ''trial multiplication''. It requires [[running time]] [[linear time|linear]] in the size of the group <math>G</math> 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 <math>G</math>.

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 <math>p</math> under addition, the power <math>b^k</math> becomes a product <math>b \cdot k</math>, and equality means congruence modulo <math>p</math> in the integers. The [[extended Euclidean algorithm]] finds <math>k</math> quickly.

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