We now present an e¬cient probabilistic algorithm that takes as input an

odd prime p, along with the prime factorization

r

e

p’1= qi i ,

i=1

and outputs a generator for Z— . It runs as follows:

p

for i ← 1 to r do

repeat

choose ± ∈ Z— at random

p

compute β ← ±(p’1)/qi

until β = 1

ei

γi ← ±(p’1)/qi

γ ← r γi

i=1

output γ

First, let us analyze the correctness of this algorithm. When the ith loop

iteration terminates, by construction, we have

e ’1

e

qi qi

γi i γi i

= 1 but = 1.

e

It follows (see Theorem 8.37) that γi has multiplicative order qi i . From this,

it follows (see Theorem 8.38) that γ has multiplicative order p ’ 1.

Thus, we have shown that if the algorithm terminates, its output is always

correct.

Let us now analyze the running time of this algorithm. Consider the

repeat/until loop in the ith iteration of the outer loop, for i = 1, . . . , r, and

let Xi be the random variable whose value is the number of iterations of

this repeat/until loop. Since ± is chosen at random from Z— , the value of

p

β is uniformly distributed over the image of the (p ’ 1)/qi -power map (see

Exercise 8.22), and since the latter is a subgroup of Z— of order qi , we see

p

that β = 1 with probability 1/qi . Thus, Xi has a geometric distribution with

associated success probability 1’1/qi , and therefore, E[Xi ] = 1/(1’1/qi ) ¤

2. Set X := X1 + · · · + Xr . Note that E[X] = E[X1 ] + · · · + E[Xr ] ¤ 2r.

The running time T of the entire algorithm is O(X · len(p)3 ), and hence

the expected running is E[T ] = O(r len(p)3 ), and since r ¤ log2 p, we have

E[T ] = O(len(p)4 ).

Finding generators and discrete logarithms in Z—

270 p

Although this algorithm is quite practical, there are asymptotically faster

algorithms for this problem (see Exercise 11.2).

Exercise 11.1. Suppose we are not given the prime factorization of p ’ 1,

but rather, just a prime q dividing p ’ 1, and we want to ¬nd an element

of multiplicative order q in Z— . Design and analyze an e¬cient algorithm to

p

do this.

Exercise 11.2. Suppose we are given a prime p, along with the prime

factorization p ’ 1 = r qi i .

e

i=1

(a) If, in addition, we are given ± ∈ Z— , show how to compute the mul-

p

tiplicative order of ± in time O(r len(p)3 ). Hint: use Exercise 8.25.

(b) Improve the running time bound to O(len(r) len(p)3 ). Hint: use Ex-

ercise 3.30.

(c) Modifying the algorithm you developed for part (b), show how to

construct a generator for Z— in expected time O(len(r) len(p)3 ).

p

Exercise 11.3. Suppose we are given a positive integer n, along with its

prime factorization n = pe1 · · · per , and that for each i = 1, . . . , r, we are also

r

1

given the prime factorization of pi ’ 1. Show how to e¬ciently compute the

multiplicative order of any element ± ∈ Z— . n

Exercise 11.4. Suppose there is an e¬cient algorithm that takes as input a

positive integer n and an element ± ∈ Z— , and computes the multiplicative

n

order of ±. Show how to use this algorithm to be build an e¬cient integer

factoring algorithm.

11.2 Computing discrete logarithms Z—

p

In this section, we consider algorithms for computing the discrete logarithm

of ± ∈ Z— to a given base γ. The algorithms we present here are, in the worst

p

case, exponential-time algorithms, and are by no means the best possible;

however, in some special cases, these algorithms are not so bad.

11.2.1 Brute-force search

Suppose that γ ∈ Z— generates a subgroup G of Z— of order q > 1 (not

p p

necessarily prime), and we are given p, q, γ, and ± ∈ G, and wish to compute

logγ ±.

The simplest algorithm to solve the problem is brute-force search:

11.2 Computing discrete logarithms Z— 271

p

β←1

i←0

while β = ± do

β ←β·γ

i←i+1

output i

This algorithm is clearly correct, and the main loop will always halt after

at most q iterations (assuming, as we are, that ± ∈ G). So the total running

time is O(q len(p)2 ).

11.2.2 Baby step/giant step method

As above, suppose that γ ∈ Z— generates a subgroup G of Z— of order q > 1

p p

(not necessarily prime), and we are given p, q, γ, and ± ∈ G, and wish to

compute logγ ±.

A faster algorithm than brute-force search is the baby step/giant step

method. It works as follows.

Let us choose an approximation m to q 1/2 . It does not have to be a very

good approximation ” we just need m = ˜(q 1/2 ). Also, let m = q/m , so

that m = ˜(q 1/2 ) as well.

The idea is to compute all the values γ i for i = 0, . . . , m ’ 1 (the “baby

steps”) and to build a “lookup table” L that contains all the pairs (γ i , i),

and that supports fast lookups on the ¬rst component of these pairs. That

is, given β ∈ Z— , we should be able to quickly determine if β = γ i for some

p

i = 0, . . . , m ’ 1, and if so, determine the value of i. Let us de¬ne L(β) := i

if β = γ i for some i = 0, . . . , m ’ 1; otherwise, de¬ne L(β) := ’1.

Using an appropriate data structure, we can build the table L in time

O(q 1/2 len(p)2 ) (just compute successive powers of γ, and insert them in

the table), and we can perform a lookup in time O(len(p)). One such data

structure is a radix tree (also called a search trie); other data structures may

be used (for example, a hash table or a binary search tree), but these may

yield slightly di¬erent running times for building the table and/or for table

lookup.

After building the lookup table, we execute the following procedure (the

“giant steps”):

Finding generators and discrete logarithms in Z—

272 p

γ ← γ ’m

β ← ±, j ← 0, i ← L(β)

while i = ’1 do

β ← β · γ , j ← j + 1, i ← L(β)