Computer Security and Cryptography

14.1 THE DISCRETE LOGARITHM PROBLEM MODULO p

If p is a prime, the set is a field. The nonzero elements form a cyclic group, meaning there exists a called a primitive root of p or a generator of such that every nonzero element of the field is a power q^k (modulo p). The sequence of powers q, q², …, q^p−1 computed modulo p are a permutation of the integers 1, 2, …, p − 1.

Example 14.1

p = 11; q = 2, 6, 7, and 8 are the only primitive roots of 11 (Table 14.1).

The discrete logarithm problem (modulo p) (DLP) is

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

Find:    x ≡ log_qy (modulo p).

A solution to the DLP modulo p can be found by exhaustive trial; that is, computing q^x (modulo p) for x = 1, 2, … until an x is found for which y = q^x (modulo p). This solution, which requires O(p) steps, is not computationally practical for p > 10¹⁰. A feasible solution technique is one for which a solution is found in steps.

The generalized discrete logarithm problem in a group is