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 qk (modulo p). The sequence of powers q, q2, …, qp−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 = qx (modulo p);
Find: x ≡ logqy (modulo p).
A solution to the DLP modulo p can be found by exhaustive trial; that is, computing qx (modulo p) for x = 1, 2, … until an x is found for which y = qx (modulo p). This solution, which requires O(p) steps, is not computationally practical for p > 1010. A feasible solution technique is one for which a solution is found in steps.
The generalized discrete logarithm problem in a group is
Get Computer Security and Cryptography now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.