p without knowing the prime factorization of p ’ 1.

As we already mentioned, all of the algorithms presented in this chapter

are completely “generic,” in the sense that they work in any ¬nite cyclic

group ” we really did not exploit any properties about Z— other than the

p

fact that it is a cyclic group. In fact, as far as such “generic” algorithms

go, the algorithms presented here for discrete logarithms are optimal [67,

93]. However, there are faster, “non-generic” algorithms (though still not

Finding generators and discrete logarithms in Z—

282 p

polynomial time) for discrete logarithms in Z— . We shall examine one such

p

algorithm later, in Chapter 16.

The “baby step/giant step” algorithm in §11.2.2 is due to Shanks [86].

See, for example, the book by Cormen, Leiserson, Rivest, and Stein [29]

for appropriate data structures to implement the lookup table used in that

algorithm. In particular, see Problem 12-2 in [29] for a brief introduction

to radix trees, which is the data structure that yields the best running time

(at least in principle) for our application.

The algorithms in §11.2.3 and §11.2.4 are variants of an algorithm pub-

lished by Pohlig and Hellman [71]. See Chapter 4 of [29] for details on how

one analyzes recursive algorithms, such as the one presented in §11.2.3; in

particular, Section 4.2 in [29] discusses in detail the notion of a recursion

tree.

The algorithm in §11.2.5 is a variant of an algorithm of Pollard [72]; in

fact, Pollard™s algorithm is a bit more e¬cient than the one presented here,

but the analysis of its running time depends on stronger heuristics. Pol-

lard™s paper also describes an algorithm for computing discrete logarithms

that lie in a restricted interval ” if the interval has width w, this algorithm

runs (heuristically) in time w1/2 len(p)O(1) , and requires space for O(len(w))

elements of Zp . This algorithm is useful in reducing the space requirement

for the algorithm of Exercise 11.13.

The key establishment protocol in §11.3 is from Di¬e and Hellman [33].

That paper initiated the study of public key cryptography, which has

proved to be a very rich ¬eld of research.

Exercises 11.13 and 11.14 are based on van Oorschot and Wiener [70].

For more on the decisional Di¬e“Hellman assumption, see Boneh [18].

12

Quadratic residues and quadratic reciprocity

12.1 Quadratic residues

For positive integer n, an integer a is called a quadratic residue modulo

n if gcd(a, n) = 1 and x2 ≡ a (mod n) for some integer x; in this case, we

say that x is a square root of a modulo n.

The quadratic residues modulo n correspond exactly to the subgroup of

squares (Z— )2 of Z— ; that is, a is a quadratic residue modulo n if and only

n n

— )2 .

if [a]n ∈ (Zn

Let us ¬rst consider the case where n = p, where p is an odd prime. In

this case, we know that Z— is cyclic of order p ’ 1 (see Theorem 9.16). Recall

p

that the subgroups any ¬nite cyclic group are in one-to-one correspondence

with the positive divisors of the order of the group (see Theorem 8.31). For

any d | (p’1), consider the d-power map on Z— that sends ± ∈ Z— to ±d . The

p p

— of order (p ’ 1)/d, and the

image of this map is the unique subgroup of Zp

kernel of this map is the unique subgroup of order d. This means that the

image of the 2-power map is of order (p ’ 1)/2 and must be the same as the

kernel of the (p ’ 1)/2-power map. Since the image of the (p ’ 1)/2-power

map is of order 2, it must be equal to the subgroup {±1}. The kernel of the

2-power map is of order 2, and so must also be equal to the subgroup {±1}.

Translating from group-theoretic language to the language of congruences,

we have shown:

Theorem 12.1. For an odd prime p, the number of quadratic residues

a modulo p, with 0 ¤ a < p, is (p ’ 1)/2. Moreover, if x is a square

root of a modulo p, then so is ’x, and any square root y of a modulo p

satis¬es y ≡ ±x (mod p). Also, for any integer a ≡ 0 (mod p), we have

a(p’1)/2 ≡ ±1 (mod p), and moreover, a is a quadratic residue modulo p if

and only if a(p’1)/2 ≡ 1 (mod p).

283

284 Quadratic residues and quadratic reciprocity

Now consider the case where n = pe , where p is an odd prime and e > 1.

We also know that Z—e is a cyclic group of order pe’1 (p ’ 1) (see Theo-

p

rem 10.1), and so everything that we said in discussing the case Z— ap-

p

plies here as well. In particular, for a ≡ 0 (mod p), a is a quadratic

e’1

residue modulo pe if and only if ap (p’1)/2 ≡ 1 (mod pe ). However,

e’1

we can simplify this a bit. Note that ap (p’1)/2 ≡ 1 (mod pe ) implies

e’1

ap (p’1)/2 ≡ 1 (mod p), and by Fermat™s little theorem, this implies

a(p’1)/2 ≡ 1 (mod p). Conversely, by Theorem 10.2, a(p’1)/2 ≡ 1 (mod p)

e’1

implies ap (p’1)/2 ≡ 1 (mod pe ). Thus, we have shown:

Theorem 12.2. For an odd prime p and integer e > 1, the number of

quadratic residues a modulo pe , with 0 ¤ a < pe , is pe’1 (p’1)/2. Moreover,

if x is a square root of a modulo pe , then so is ’x, and any square root y of

a modulo pe satis¬es y ≡ ±x (mod pe ). Also, for any integer a ≡ 0 (mod p),

e’1

we have ap (p’1)/2 ≡ ±1 (mod p), and moreover, a is a quadratic residue

e’1

modulo pe i¬ ap (p’1)/2 ≡ 1 (mod pe ) i¬ a(p’1)/2 ≡ 1 (mod p) i¬ a is a

quadratic residue modulo p.

Now consider an arbitrary odd integer n > 1, and let n = r pei be its

i=1 i

prime factorization. Recall the group isomorphism implied by the Chinese

remainder theorem:

Z— ∼ Z—e1 — · · · — Z—er .

= n pr

p1

Now,

(±1 , . . . , ±r ) ∈ Z—e1 — · · · — Z—er

pr

p

1

is a square if and only if there exist β1 , . . . , βr with βi ∈ Z—ei and ±i = βi

2

p i

for i = 1, . . . , r, in which case, we see that the square roots of (±1 , . . . , ±r )

comprise the 2r elements (±β1 , . . . , ±βr ). Thus we have:

Theorem 12.3. Consider an odd, positive integer n with prime factoriza-

tion n = r pei . The number of quadratic residues a modulo n, with

i=1 i

0 ¤ a < n, is φ(n)/2r . Moreover, if a is a quadratic residue modulo n,

then there are precisely 2r distinct integers x, with 0 ¤ x < n, such that

x2 ≡ a (mod n). Also, an integer a is a quadratic residue modulo n if and

only if it is a quadratic residue modulo pi for i = 1, . . . , r.

That completes our investigation of the case where n is odd. We shall

not investigate the case where n is even, as it is a bit messy, and is not of

particular importance.

12.2 The Legendre symbol 285

12.2 The Legendre symbol

For an odd prime p and an integer a with gcd(a, p) = 1, the Legendre

symbol (a | p) is de¬ned to be 1 if a is a quadratic residue modulo p, and ’1

otherwise. For completeness, one de¬nes (a | p) = 0 if p | a. The following

theorem summarizes the essential properties of the Legendre symbol.

Theorem 12.4. Let p be an odd prime, and let a, b ∈ Z. Then we have

(i) (a | p) ≡ a(p’1)/2 (mod p); in particular, (’1 | p) = (’1)(p’1)/2 ;