Algorithms
See also: discrete logarithm records| Can the discrete logarithm be computed in polynomial time on a classical computer? |
No efficient classical algorithm for computing general discrete logarithms logb g is known. The naive algorithm is to raise b to higher and higher powers k until the desired g is found; this is sometimes called trial multiplication. This algorithm requires running time linear in the size of the group G and thus exponential in the number of digits in the size of the group. There exists an efficient quantum algorithm due to Peter Shor.
More sophisticated algorithms exist, usually inspired by similar algorithms for integer factorization. These algorithms run faster than the naive algorithm, but none of them runs in polynomial time (in the number of digits in the size of the group).
- Baby-step giant-step
- Pollard's rho algorithm for logarithms
- Pollard's kangaroo algorithm (aka Pollard's lambda algorithm)
- Pohlig–Hellman algorithm
- Index calculus algorithm
- Number field sieve
- Function field sieve
Read more about this topic: Discrete Logarithm
Related Phrases
Related Words