by either performing the exponentiation a(p’1)/2 mod p or by computing the

Legendre symbol (a | p). Assume that 0 ¤ a < p. Using a standard repeated

squaring algorithm, the former method takes time O(len(p)3 ), while using

the Euclidean-like algorithm of the previous section, the latter method takes

time O(len(p)2 ). So clearly, the latter method is to be preferred.

13.2.2 Prime-power modulus

For an odd prime p, we know that a is a quadratic residue modulo pe if and

only if a is a quadratic residue modulo p. So this case immediately reduces

to the previous case.

13.2.3 Composite modulus

For odd, composite n, if we know the factorization of n, then we can also de-

termine if a is a quadratic residue modulo n by determining if it is a quadratic

residue modulo each prime divisor p of n. However, without knowledge of

this factorization (which is in general believed to be hard to compute), there

is no e¬cient algorithm known. We can compute the Jacobi symbol (a | n);

292 Computational problems related to quadratic residues

if this is ’1 or 0, we can conclude that a is not a quadratic residue; otherwise,

we cannot conclude much of anything.

13.3 Computing modular square roots

In this section, we consider the problem of computing a square root of a

modulo n, given integers a and n, where a is a quadratic residue modulo n.

13.3.1 Prime modulus

Let p be an odd prime, and let a be an integer such that 0 < a < p and

(a | p) = 1. We would like to compute a square root of a modulo p. Let

± := [a]p ∈ Z— , so that we can restate our problem of that of ¬nding β ∈ Z—

p p

2 = ±, given ± ∈ (Z— )2 .

such that β p

We ¬rst consider the special case where p ≡ 3 (mod 4), in which it turns

out that this problem can be solved very easily. Indeed, we claim that in

this case

β := ±(p+1)/4

is a square root of ± ”note that since p ≡ 3 (mod 4), the number (p + 1)/4

˜ ˜

is an integer. To show that β 2 = ±, suppose ± = β 2 for some β ∈ Z— . We

p

˜ since we are assuming that ± ∈ (Z— )2 . Then

know that there is such a β, p

we have

˜ ˜

β 2 = ±(p+1)/2 = β p+1 = β 2 = ±,

where we used Fermat™s little theorem for the third equality. Using a

repeated-squaring algorithm, we can compute β in time O(len(p)3 ).

Now we consider the general case, where we may have p ≡ 3 (mod 4).

Here is one way to e¬ciently compute a square root of ±, assuming we are

given, in addition to ±, an auxiliary input γ ∈ Z— \ (Z— )2 (how one obtains

p p

such a γ is discussed below).

Let us write p ’ 1 = 2h m, where m is odd. For any δ ∈ Z— , δ m has mul-

p

h’1 m

tiplicative order dividing 2h . Since ±2 = 1, ±m has multiplicative order

h’1 m

dividing 2h’1 . Since γ 2 = ’1, γ m has multiplicative order precisely

2h . Since there is only one subgroup of Z— of order 2h , it follows that γ m

p

generates this subgroup, and that ±m = γ mx for 0 ¤ x < 2h and x is even.

We can ¬nd x by computing the discrete logarithm of ±m to the base γ m ,

using the algorithm in §11.2.3. Setting κ = γ mx/2 , we have

κ2 = ± m .

13.3 Computing modular square roots 293

We are not quite done, since we now have a square root of ±m , and not of

±. Since m is odd, we may write m = 2t + 1 for some non-negative integer

t. It then follows that

(κ±’t )2 = κ2 ±’2t = ±m ±’2t = ±m’2t = ±.

Thus, κ±’t is a square root of ±.

Let us summarize the above algorithm for computing a square root of

± ∈ (Z— )2 , assuming we are given γ ∈ Z— \ (Z— )2 , in addition to ±:

p p p

Compute positive integers m, h such that p ’ 1 = 2h m with m odd

γ ← γ m , ± ← ±m

Compute x ← logγ ± // note that 0 ¤ x < 2h and x is even

β ← (γ )x/2 ±’ m/2

output β

The total amount of work done outside the discrete logarithm calcu-

lation amounts to just a handful of exponentiations modulo p, and so

takes time O(len(p)3 ). The time to compute the discrete logarithm is

O(h len(h) len(p)2 ). So the total running time of this procedure is

O(len(p)3 + h len(h) len(p)2 ).

The above procedure assumed we had at hand a non-square γ. If h = 1,

which means that p ≡ 3 (mod 4), then (’1 | p) = ’1, and so we are done.

However, we have already seen how to e¬ciently compute a square root in

this case.

If h > 1, we can ¬nd a non-square γ using a probabilistic search algorithm.

Simply choose γ at random, test if it is a square, and if so, repeat. The

probability that a random element of Z— is a square is 1/2; thus, the expected

p

number of trials until we ¬nd a non-square is 2, and hence the expected

running time of this probabilistic search algorithm is O(len(p)2 ).

Exercise 13.3. Let p be an odd prime, and let f ∈ Zp [X] be a polynomial

with 0 ¤ deg(f ) ¤ 2. Design and analyze an e¬cient, probabilistic algo-

rithm that determines if f has any roots in Zp , and if so, ¬nds all of the

roots. Hint: see Exercise 9.14.

Exercise 13.4. Show that the following two problems are deterministic,

poly-time equivalent (see discussion just above Exercise 11.10 in §11.3):

(a) Given an odd prime p and ± ∈ (Z— )2 , ¬nd β ∈ Z— such that β 2 = ±.

p p

(b) Given an odd prime p, ¬nd an element of Z— \ (Z— )2 .

p p

294 Computational problems related to quadratic residues

Exercise 13.5. Design and analyze an e¬cient, deterministic algorithm

that takes as input primes p and q, such that q | (p ’ 1), along with an

element ± ∈ Z— , and determines whether or not ± ∈ (Z— )q .

p p

Exercise 13.6. Design and analyze an e¬cient, deterministic algorithm

that takes as input primes p and q, such that q | (p ’ 1) but q 2 (p ’ 1),

along with an element ± ∈ (Z— )q , and computes a qth root of ±, that is, an

p

— such that β q = ±.

element β ∈ Zp

Exercise 13.7. We are given a positive integer n, two elements ±, β ∈ Zn ,

and integers e and f such that ±e = β f and gcd(e, f ) = 1. Show how

to e¬ciently compute γ ∈ Zn such that γ e = β. Hint: use the extended

Euclidean algorithm.

Exercise 13.8. Design and analyze an algorithm that takes as input primes

p and q, such that q | (p’1), along with an element ± ∈ (Z— )q , and computes

p

2 | (p ’ 1).) Your

a qth root of ±. (Unlike Exercise 13.6, we now allow q

algorithm may be probabilistic, and should have an expected running time

that is bounded by q 1/2 times a polynomial in len(p). Hint: the previous

exercise may be useful.

Exercise 13.9. Let p be an odd prime, γ be a generator for Z— , and ± be

p

— . De¬ne

any element of Zp

1 if logγ ± ≥ (p ’ 1)/2;

B(p, γ, ±) :=

0 if logγ ± < (p ’ 1)/2.

Suppose that there is an algorithm that e¬ciently computes B(p, γ, ±) for

all p, γ, ± as above. Show how to use this algorithm as a subroutine in

an e¬cient, probabilistic algorithm that computes logγ ± for all p, γ, ± as

above. Hint: in addition to the algorithm that computes B, use algorithms