Algorithmic Number Theory for Cryptography and Cryptanalysis: Primality, Factoring and Discrete Logarithms - Introduction to Cryptography with Maple - page 368

6.5 The Discrete Logarithm Problem

We continue our examination of number-theoretic “difficult problems” with a view
towards using them as the basis of cryptographic schemes. After the integer factor-
ization problem, the most widely used problem of this type is the discrete logarithm
problem (DLP).
We have already met the DLP when discussing one-way functions in Sect. 3.3.2
and we will meet it again soon when discussing the security of the DH protocol
in Chap. 7 . The most general version of the DLP takes place in a group G whose
operation can be carried out efficiently. More explicitly, this implies that we have
representations of the group elements by strings in such a way that it is easy to check
whether a string represents the identity element and whether two strings represent
the same element. Moreover, this also means that we have efficient algorithms to
compute the string representing the product of two elements or the inverse of an
element. This assumption, together with the binary exponentiation method discussed
in Chap. 2 (therein used for modular exponentiation but obviously working in any
group) implies that exponentiation in G is also efficient.
An instance of the DLP in a group G is then as follows. Given G and elements

g =

g x . If the order of g is n then, as we have seen in Chap. 3 , the discrete logarithm
function dlog ( g , g ) :

∈ G , a ∈ G , such that a ∈ g , find a non-negative integer x such that a

g →Z n is the inverse of the discrete exponential function

g x , where both functions are
group isomorphisms. An instance of the DLP is then to find the image of an element
a

dexp ( g , g ) : Z n → g , given by dexp ( g , g ) ( x ) =

∈

. This image is called the discrete logarithm—or
the index—of a to the base g and is denoted log g a . The interest of the DLP for
cryptography comes from the fact that, while computing the function dexp is easy
with the binary method, computing the function dlog is regarded as difficult for
some groups.

g by the function dlog ( g , g )

Remark 6.9 Observe that log g is just a shorter name for the function dlog ( g , g ) :

→Z n , where the cyclic group and its order are understood, and the fact that
this function is a group homomorphism can be expressed as the usual logarithmic
formula log g ab

g

= log g a + log g b for all a , b ∈ g , where g ∈ G has order n and

the sum is in Z n , i.e., sum of integers modulo n .

Exercise 6.30 Prove that the following “change of base” formula holds: if g =

g ⊆ log g g · G is a cyclic subgroup of G of order n and a ∈ g , then log g a = (

log g a ) mod n .

We will study a few algorithms to solve the DLP and we start by pointing out that
these algorithms fall into two classes: the generic algorithms that do not depend on
any special properties of the encoding of the elements of the group as strings and
hence work for arbitrary groups, and the group-specific algorithms which work only
for specific groups whose additional properties they exploit. In the case of generic
algorithms we may assume that G = g is cyclic because otherwise the elements