Pohlig–Hellman algorithm

The Pohlig -Hellman algorithm was named after the mathematicians Stephen Pohlig and Martin Hellman. Occasionally, this algorithm found in the literature under the name of Silver - Pohlig -Hellman algorithm. To the Pohlig -Hellman algorithm, the discrete logarithm can be calculated in a cyclic group.

The relevance of this method is that the computational complexity does not depend on the group order, but the biggest factor of the group order. The disadvantage is that a prime factorization of the group order must be known for this procedure. Such a factorization is in general, however, very difficult to determine.

Mathematical Background

Let be a cyclic group of order, with the factorisation of known and the biggest factor of whether. The discrete logarithm in the group can then be calculated by means of Silver - Pohlig -Hellman in place operations. This is done in three steps:

The algorithm

Let G be the cyclic group of order n, g is a generator of G and. Next is the prime factorization of n

The algorithm is now shown in two steps. First, a version for groups whose order corresponds to a prime power. It can be used in the following as a Pohlig -Hellman algorithm in general.

Prime -power Pohlig -Hellman

The group order is, where is a prime number. To determine the discrete logarithm in subgroups of the baby-step giant-step algorithm of Shanks will be used.

In this algorithm, the discrete logarithm in the following form may be written: . Due to the restrictions made ​​this representation is unique.

General Pohlig -Hellman

Credentials

• Theoretical number algorithm