positive constant D, we have

Dy δ / log y ¤ |V | ¤ y δ ,

and taking logarithms, and again using the fact that u ’ ∞, we have

log |V | ’ δ log y = O(log log y) = o(u log log x). 2

16.2 An algorithm for discrete logarithms

We now present a probabilistic, subexponential-time algorithm for comput-

ing discrete logarithms. The input to the algorithm is p, q, γ, ±, where p and

q are primes, with q | (p ’ 1), γ is an element of Z— generating a subgroup

p

— of order q, and ± ∈ G.

G of Zp

338 Subexponential-time discrete logarithms and factoring

We shall make the simplifying assumption that q 2 (p ’ 1), which is

equivalent to saying that q m := (p’1)/q. Although not strictly necessary,

this assumption simpli¬es the design and analysis of the algorithm, and

moreover, for cryptographic applications, this assumption is almost always

satis¬ed. (Exercises 16.1“16.3 below explore how this assumption may be

lifted, as well as other generalizations.)

At a high level, the main goal of our discrete logarithm algorithm is to

¬nd a random representation of 1 with respect to γ and ± ” as discussed

in Exercise 11.12, this allows us to compute logγ ± (with high probability).

More precisely, our main goal is to compute integers r and s in a probabilistic

fashion, such that γ r ±s = 1 and [s]q is uniformly distributed over Zq . Having

accomplished this, then with probability 1’1/q, we shall have s ≡ 0 (mod q),

which allows us to compute logγ ± as ’rs’1 mod q.

Let G be the subgroup of Z— of order m. Our assumption that q m

p

implies that G © G = {1}, since the multiplicative order of any element in

the intersection must divide both q and m, and so the only possibility is

that the multiplicative order is 1. Therefore, the map ρ : G — G ’ Z— that

p

— | = qm, it must

sends (β, δ) to βδ is injective (Theorem 8.28), and since |Zp

be surjective as well.

We shall use this fact in the following way: if β is chosen uniformly

at random from G, and δ is chosen uniformly at random from G (and

independent of β), then βδ is uniformly distributed over Z— . Furthermore,

p

— , we may generate a random

since G is the image of the q-power map on Zp

ˆ ˆ

δ ∈ G simply by choosing δ ∈ Z— at random, and setting δ := δ q .

p

The discrete logarithm algorithm uses a “smoothness parameter” y, whose

choice will be discussed below when we analyze the running time of the algo-

rithm; for now, we only assume that y < p. Let p1 , . . . , pk be an enumeration

of the primes up to y. Let πi := [pi ]p ∈ Z— for i = 1, . . . , k.

p

The algorithm has two stages.

In the ¬rst stage, we ¬nd relations of the form

e

e

γ ri ±si δi = π1i1 . . . πkik , (16.2)

for integers ri , si , ei1 , . . . , eik , and δi ∈ G , and i = 1, . . . , k + 1.

We obtain one such relation by a randomized search, as follows: we choose

ˆ

ri , si ∈ {0, . . . , q ’ 1} at random, as well as δi ∈ Z— at random; we then

p

ˆq , βi := γ ri ±si , and mi := rep(βi δi ). Now, the value βi

compute δi := δi

is uniformly distributed over G, while δi is uniformly distributed over G ;

therefore, the product βi δi is uniformly distributed over Z— , and hence mi p

16.2 An algorithm for discrete logarithms 339

is uniformly distributed over {1, . . . , p ’ 1}. Next, we simply try to factor

mi by trial division, trying all the primes p1 , . . . , pk up to y. If we are lucky,

we completely factor mi in this way, obtaining a factorization

mi = pei1 · · · peik ,

1 k

for some exponents ei1 , . . . , eik , and we get the relation (16.2). If we are

unlucky, then we simply try (and try again) until we are lucky.

For i = 1, . . . , k + 1, let vi := (ei1 , . . . , eik ) ∈ Z—k , and let vi denote the

¯

image of vi in Z—k (i.e., vi := ([ei1 ]q , . . . , [eik ]q )). Since Z—k is a vector space

¯

q q

over the ¬eld Zq of dimension k, the vectors v1 , . . . , vk+1 must be linearly de-

¯ ¯

pendent. The second stage of the algorithm uses Gaussian elimination over

Zq (see §15.4) to ¬nd a linear dependence among the vectors v1 , . . . , vk+1 ,

¯ ¯

that is, to ¬nd integers c1 , . . . , ck+1 ∈ {0, . . . , q ’ 1}, not all zero, such that

(e1 , . . . , ek ) := c1 v1 + · · · ck+1 vk+1 ∈ qZ—k .

Raising each equation (16.2) to the power ci , and multiplying them all

together, we obtain

e

e

γ r ±s δ = π11 · · · πkk ,

where

k+1 k+1 k+1

c

δi i .

r := ci ri , s := ci si , and δ :=

i=1 i=1 i=1

e

Now, δ ∈ G , and since each ei is a multiple of q, we also have πi i ∈ G

for i = 1, . . . , k. It follows that γ r ±s ∈ G . But since γ r ±s ∈ G as well, and

G © G = {1}, it follows that γ r ±s = 1. If we are lucky (and we will be with

overwhelming probability, as we discuss below), we will have s ≡ 0 (mod q),

in which case, we can compute s := s’1 mod q, obtaining

± = γ ’rs ,

and hence ’rs mod q is the discrete logarithm of ± to the base γ. If we

are very unlucky, we will have s ≡ 0 (mod q), at which point the algorithm

simply quits, reporting “failure.”

The entire algorithm, called Algorithm SEDL, is presented in Fig. 16.1.

As already argued above, if Algorithm SEDL does not output “failure,”

then its output is indeed the discrete logarithm of ± to the base γ. There

remain three questions to answer:

1. What is the expected running time of Algorithm SEDL?

340 Subexponential-time discrete logarithms and factoring

i←0

repeat

i←i+1

repeat

choose ri , si ∈ {0, . . . , q ’ 1} at random

ˆ

choose δi ∈ Z— at random

p

ri ±si , δ ← δ q , m ← rep(β δ )

ˆ

βi ← γ i i ii

i

test if mi is y-smooth (trial division)

until mi = p1i1 · · · peik for some integers ei1 , . . . , eik

e

k

until i = k + 1

set vi ← (ei1 , . . . , eik ) ∈ Z—k for i = 1, . . . , k + 1

apply Gaussian elimination over Zq to ¬nd integers c1 , . . . , ck+1 ∈

{0, . . . , q ’ 1}, not all zero, such that

c1 v1 + · · · + ck+1 vk+1 ∈ qZ—k .

k+1 k+1

r← s←

i=1 ci ri , i=1 ci si

if s ≡ 0 (mod q) then

output “failure”

else

output ’rs’1 mod q

Fig. 16.1. Algorithm SEDL