Computer Security and Cryptography

14.2 SOLUTION OF THE DLP MODULO p GIVEN A FACTORIZATION OF p − 1

The Pohlig–Hellman Algorithm [Pohlig and Hellman, 1978] for solving the discrete logarithm problem modulo p assumes the factorisation of p − 1 is known:

Given:    a primitive root of p, and y = q^x (modulo p);

Find:   x = log_p y (modulo p).

The important observation is that it suffices to solve the DLP if x is replaced by its residues modulo for each prime factor. Write the base- representation of x for the prime factor of p − 1:

where C is some (positive) integer. Then, for 1 ≤ i ≤ k

As is an integer, Fermat's Little Theorem gives (modulo p) so that

The Pohlig–Hellman Algorithm determines the base-p_i digits {x_{i, j}} for each ...