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

also hard to check if a given y ∈ Z n is in G or not. If y ∈ G , it is still hard to compute
one x such that y = g x mod n .

In many cases, we can adapt factorization algorithms to solve all these problems.
Here we first see that when # G and its factorization are known (which is the DLKO FP
problem) and when # G is B -smooth, we can have a simple algorithm within O ( √ B )
arithmetic operations.

7.4.1 Pollard Rho Method

The heuristic Pollard Rho factorization algorithm, described in Section 7.2.1, can be
adapted to solve the discrete logarithm problem when we are given the order of the
group (i.e. the above DLKOP) (see Ref. [150]).

Let G denote the (multiplicatively denoted) group, n denote its order, g and y be
two elements of G such that we look for some integer c such that y = g c . The idea
consists in managing a sequence of ( x ,α,β ) triplets such that x = g α y β . The sequence is
obtaine d by some kind of random walk. We expect to loop on the x term of the triplet
in O ( √ n ) iterations, so that we obtain an equation of the kind

g α y β

g α y β = x =

which leads us to

= α − α
β − β

c mod n .

The random walk is defined by a function f ( x ,α, β ) by

⎧
⎨
⎩

( x × g ,α + 1 mod n , β ) if h ( x ) = 1

f ( x ,α, β ) =

( x × y ,α, β + 1 mod n ) if h ( x ) = 2

( x 2

, 2 α mod n , 2 β mod n )

if h ( x ) = 3

where h is a random balanced function from G to { 1 , 2 , 3 } . We can easily see that the
property x = g α y β is preserved by replacing ( x ,α, β ) by f ( x ,α, β ) . Analysis shows t ha t
this is indeed a random walk so that we are expected to loop on the first term in O ( √ n ) .
The complete algorithm is detailed in Fig. 7.8.

7.4.2 Shanks Baby Steps - Giant Steps Algorithm

We now describe the Shanks baby step - g iant step algorithm which solves the DLKOP
problem within a complexity of O ( √ # G ) . It even solves t he DLP problem when we
have an upper bound B for # G , within a complexity of O ( √ B ) . It is also convenient for
finding element orders (which are a kind of discrete logarithm of unity).