Discrete logarithm problem

From Groupprops
Jump to: navigation, search

Definition

This problem usually makes sense in the context of an encoding of a group or a multi-encoding of a group. The problem asks for the following: given the code-words for elements g,h of the group such that h is a power of g, find any integer x such that g^x = h.

In the context of a black-box cyclic group, this problem is typically asked with g chosen to be a generator of the group.

Caveat

Note that x is unique modulo the order of g. Usually, the problem is discussed in a context where the order of g is known, i.e., we already know the answer to the element order-finding problem for g. Given this information, finding one value of x is equivalent to finding all values of x.

However, the problem makes sense even when the order of g is not known. In this case, an algorithm that gives any x (not necessarily the smallest positive value) suffices.