linguistic:voice_change
Algorithms

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 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 in the size of the group G and thus 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).

There is an efficient quantum algorithm due to Peter Shor.

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

With 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, i.e. has no large prime factors.