2. How should the smoothness parameter y be chosen so as to minimize

the expected running time?

3. What is the probability that Algorithm SEDL outputs “failure”?

Let us address these questions in turn. As for the expected running time,

let σ be the probability that a random element of {1, . . . , p ’ 1} is y-smooth.

Then the expected number of attempts needed to produce a single relation

is σ ’1 , and so the expected number of attempts to produce k + 1 relations

is (k + 1)σ ’1 . In each attempt, we perform trial division using p1 , . . . , pk ,

along with a few other minor computations, leading to a total expected

running time in stage 1 of k 2 σ ’1 · len(p)O(1) . The running time in stage

2 is dominated by that of the Gaussian elimination step, which takes time

k 3 · len(p)O(1) . Thus, if T is the total running time of the algorithm, then

we have

E[T ] ¤ (k 2 σ ’1 + k 3 ) · len(p)O(1) . (16.3)

16.2 An algorithm for discrete logarithms 341

Let us assume for the moment that

y = exp[(log p)»+o(1) ] (16.4)

for some constant » with 0 < » < 1. Our ¬nal choice of y will indeed satisfy

this assumption. Consider the probability σ. We have

σ = Ψ(y, p ’ 1)/(p ’ 1) = Ψ(y, p)/(p ’ 1) ≥ Ψ(y, p)/p,

where for the second equality we use the assumption that y < p, so p is not

y-smooth. With our assumption (16.4), we may apply Theorem 16.1 (with

the given value of y and x := p), obtaining

σ ≥ exp[(’1 + o(1))(log p/ log y) log log p].

By Chebyshev™s theorem (Theorem 5.1), we know that k = ˜(y/ log y), and

so log k = (1 + o(1)) log y. Moreover, assumption (16.4) implies that the

factor len(p)O(1) in (16.3) is of the form exp[o(min(log y, log p/ log y))], and

so we have

E[T ] ¤ exp[(1 + o(1)) max{(log p/ log y) log log p + 2 log y, 3 log y}]. (16.5)

Let us ¬nd the value of y that minimizes the right-hand side of (16.5),

ignoring the “o(1)” terms. Let µ := log y, A := log p log log p, S1 := A/µ +

2µ, and S2 := 3µ. We want to ¬nd µ that minimizes max{S1 , S2 }. Using

a little calculus, one sees that√ 1 is minimized at µ = (A/2)1/2 . With this

S √

choice of µ, we have S1 = (2 2)A1/2 and S2 = (3/ 2)A1/2 < S1 . Thus,

choosing

√

y = exp[(1/ 2)(log p log log p)1/2 ],

we obtain

√

E[T ] ¤ exp[(2 2 + o(1))(log p log log p)1/2 ].

That takes care of the ¬rst two questions, although strictly speaking, we

have only obtained an upper bound for the expected running time, and we

have not shown that the choice of y is actually optimal, but we shall never-

theless content ourselves (for now) with these results. Finally, we deal with

the third question, on the probability that the algorithm outputs “failure.”

Lemma 16.2. The probability that the algorithm outputs “failure” is 1/q.

Proof. Consider the values ri , si , and βi generated in the inner loop in stage

1. It is easy to see that, as random variables, the values si and βi are inde-

pendent, since conditioned on any ¬xed choice of si , the value ri is uniformly

distributed over {0, . . . , q ’ 1}, and hence βi is uniformly distributed over

342 Subexponential-time discrete logarithms and factoring

G. Turning this around, we see that conditioned on any ¬xed choice of βi ,

the value si is uniformly distributed over {0, . . . , q ’ 1}.

So now let us condition on any ¬xed choice of values βi and δi , for

i = 1, . . . , k + 1, as determined at the end of stage 1 of the algorithm.

By the remarks in the previous paragraph, we see that in this condi-

tional probability distribution, the variables si are mutually independent

and uniformly distributed over {0, . . . , q ’ 1}, and moreover, the behav-

ior of the algorithm is completely determined, and in particular, the values

c1 , . . . , ck+1 are ¬xed. Therefore, in this conditional probability distribution,

the probability that the algorithm outputs failure is just the probability that

i si ci ≡ 0 (mod q), which is 1/q, since not all the ci are zero modulo q.

Since this equality holds for every choice of βi and δi , the lemma follows. 2

Let us summarize the above discussion in the following theorem.

Theorem 16.3. With the smoothness parameter set as

√

y := exp[(1/ 2)(log p log log p)1/2 ],

the expected running time of Algorithm SEDL is

√

exp[(2 2 + o(1))(log p log log p)1/2 ].

The probability that Algorithm SEDL outputs “failure” is 1/q.

In the description and analysis of Algorithm SEDL, we have assumed that

the primes p1 , . . . , pk were pre-computed. Of course, we can construct this

list of primes using, for example, the sieve of Eratosthenes (see §5.4), and

the running time of this pre-computation will be dominated by the running

time of Algorithm SEDL.

In the analysis of Algorithm SEDL, we relied crucially on the fact that

in generating a relation, each candidate element γ ri ±si δi was uniformly dis-

tributed over Z— . If we simply left out the δi , then the candidate element

p

would be uniformly distributed over the subgroup G, and Theorem 16.1

simply would not apply. Although the algorithm might anyway work as

expected, we would not be able to prove this.

Exercise 16.1. Using the result of Exercise 15.14, show how to modify

Algorithm SEDL to work in the case where p ’ 1 = q e m, e > 1, q m, γ

generates the subgroup G of Z— of order q e , and ± ∈ G. Your algorithm

p

should compute logγ ± with roughly the same expected running time and

success probability as Algorithm SEDL.

16.2 An algorithm for discrete logarithms 343

Exercise 16.2. Using the algorithm of the previous exercise as a subroutine,

design and analyze an algorithm for the following problem. The input is

p, q, γ, ±, where p is a prime, q is a prime dividing p ’ 1, γ generates the

subgroup G of Z— of order q, and ± ∈ G; note that we may have q 2 | (p ’ 1).

p

The output is logγ ±. Your algorithm should always succeed in computing

this discrete logarithm, and its expected running time should be bounded by

a constant times the expected running time of the algorithm of the previous

exercise.

Exercise 16.3. Using the result of Exercise 15.15, show how to modify

Algorithm SEDL to solve the following problem: given a prime p, a generator

γ for Z— , and an element ± ∈ Z— , compute logγ ±. Your algorithm should

p p

work without knowledge of the factorization of p ’ 1; its expected running

time should be roughly the same as that of Algorithm SEDL, but its success

probability may be lower. In addition, explain how the success probability

may be signi¬cantly increased at almost no cost by collecting a few extra

relations.

Exercise 16.4. Let n = pq, where p and q are distinct, large primes. Let e

be a prime, with e < n and e (p ’ 1)(q ’ 1). Let x be a positive integer,

with x < n. Suppose you are given n (but not its factorization!) along with

e and x. In addition, you are given access to two “oracles,” which you may

invoke as often as you like.

• The ¬rst oracle is a “challenge oracle”: each invocation of the oracle

produces a “challenge” a ∈ {1, . . . , x} ” distributed uniformly and

independently of all other challenges.

• The second oracle is a “solution oracle”: you invoke this oracle with

the index of a previous challenge oracle; if the corresponding challenge

was a, the solution oracle returns the eth root of a modulo n; that

is, the solution oracle returns b ∈ {1, . . . , n ’ 1} such that be ≡

a (mod n) ”note that b always exists and is uniquely determined.

Let us say that you “win” if you are able to compute the eth root modulo

n of any challenge, but without invoking the solution oracle with the cor-

responding index of the challenge (otherwise, winning would be trivial, of

course).

(a) Design a probabilistic algorithm that wins the above game, using an

expected number of

exp[(c + o(1))(log x log log x)1/2 ] · len(n)O(1)

steps, for some constant c, where a “step” is either a computation step

344 Subexponential-time discrete logarithms and factoring

or an oracle invocation (either challenge or solution). Hint: Gaussian

elimination over the ¬eld Ze .

(b) Suppose invocations of the challenge oracle are “cheap,” while invo-

cations of the solution oracle are relatively “expensive.” How would

you modify your strategy in part (a)?