Algorithmic Number Theory - A Classical Introduction to Cryptography: Applications for Communications Security - page 200

but it is not quite clear whether one of the first two reductions is actually an equivalence
or not. We can still suspect that knowledge of λ ( n ) and knowledge of the factorization
of λ ( n ) are not equivalent given the hardness of the factorization problem, but this is
not so obvious since the integer has a particular form and we have a hint with the extra
information of the knowledge of n .

In Section 7.4 we will present an algorithm computing element orders in O ( √ # G )
time when we do not know # G .

7.4 Discrete Logarithm

Another problem similar to factorization and widely used in cryptography is the discrete
logarithm problem : in a multiplicative group G generated by some g , compute an integer
x such that y = g x from y ∈ G . We summarize this by saying that we want to compute
log g y in G . There are a few variants.

The order # G of the group can be available or not.
Since the logarithm is in unique modulo # G , we can ask for one possible logarithm
if # G is not available.
The y elements may not necessarily be in G and in that case, the problem consists
of distinguishing elements of G from other elements.
and so on.

Here are some formal problem specifications.

DLP (Discrete Logarithm Problem):
Parameters : a cyclic group G generated by an element g ∈ G
Input : an element y in G
Problem : compute the least integer x such that y = g x
DLKOP (Discrete Logarithm with Known Order Problem):
Parameters : a cyclic group G generated by an element g ∈ G , and the order
# G
Input : an element y in G
Problem : compute x such that y = g x

Note that if the order of G is known, then computing the least discrete logarithm and
computing one representative are two equivalent problems. We can also consider the
problem when the factorization of the order of G is known.

DLKOFP (Discrete Logarithm with Known Order Factorization Problem):
Parameters : a

cyclic group G generated by an element g ∈ G , the order

# G and its factorization into prime numbers
Input : an element y in G
Problem : compute x such that y = g x

As an example, we can consider the multiplicative group G generated by some

∈ Z n .If ϕ ( n ) is unknown, it is quite hard to compute the order of g in general. It is g