62 Square Roots Modulo the Product of Two Primes

Proof: Consider the mapping sq : Z*_n → QR_n defined by bb² mod n. We show that this is a 4-to-1 mapping from Z*_n onto QR_n.

Let a QR_n and let b² ≡ a (mod n) be a square root of a. Then also b² ≡ a (mod p) and b² ≡ a (mod q), so b is a square root of a (mod p) and b is a square root of a (mod q). Conversely, if b_p is a square root of a (mod p) and b_q is a square root of a (mod q), then by the Chinese Remainder theorem, the unique number b Z*_n such that b ≡ b_p (mod p) and b ≡ b_q (mod q) is a square root of a (mod n). Since a has two square roots mod p and two square roots mod q, it follows that a has four square roots mod n. Thus, sq() is a 4-to-1 function, and ∣QR_n∣ = ∣Z*_n∣ as desired. __

63 Euler Criterion

There is a simple test due to Euler for whether a number is in QR_p for p prime.

Claim 2 (Euler Criterion): An integer a is a non-trivial¹ quadratic residue modulo p iff

Proof: Let a ≡ b² (mod p) for some b ⁄≡ 0 (mod p). Then

by Euler’s theorem, as desired.

For the other direction, suppose a^(p-1)∕2 ≡ 1 (mod p). Clearly a ⁄≡ 0 (mod p). We show that a is a quadratic residue by finding a square root b modulo p.

Let g be a primitive root of p. Choose k so that a ≡ g^k (mod p), and let ℓ = (p - 1)k∕2. Then

Because g is a primitive root, g^ℓ ≡ 1 (mod p) implies that ℓ is a multiple of p - 1. Hence, (p - 1) ∣ (p - 1)k∕2, from which we conclude that 2∣k and k∕2 is an integer. Let b = g^k∕2. Then b² ≡ g^k ≡ a (mod p), so b is a square root of a modulo p, as desired. __

64 Finding Square Roots Modulo Special Primes

The Euler criterion lets us test membership in QR_p for prime p, but it doesn’t tell us how to find square roots. In case p ≡ 3 (mod 4), there is an easy algorithm for finding the square roots of any member of QR_p.

Proof: Under the assumptions of the claim, p + 1 is divisible by 4, so (p + 1)∕4 is an integer. Then

by the Euler Criterion (Claim 2). __

65 Shank’s Algorithm for Finding Square Roots Modulo Odd Primes

Let p be an odd prime. It can be written uniquely as p = 2ⁿq + 1, where n and q are integers and q is odd. (Note that n is simply the number of trailing 0’s in the binary expansion of p, and q is what results when p is shifted right by n places.) Because p is odd, p - 1 is even, so n ≥ 1. Section 64 treats the special case where n = 1. We now present an algorithm due to D. Shanks² that works for all n.

Let p,n,q be as above. Assume a is a quadratic residue and u is a quadratic non-residue modulo p. (We can easily find u by choosing random elements of Z*_p and applying the Euler Criterion.) The goal is to find x such that x² ≡ a (mod p).

Input: Odd prime p, quadratic residue a QRp.

The congruence x² ≡ ab (mod p) is easily shown to be a loop invariant. Hence, if the program terminates, x is a square root of a.

To see why it terminates after at most n iterations of the loop, we look at the orders³ of b and z (mod p) at the start of each loop iteration (before line 8) and show that ord(b) < ord(z) = 2^k.

On the first iteration, k = n, z = u^q, and ord(z) = 2ⁿ. Clearly

so ord(z)∣2ⁿ. By the Euler Criterion, since u is a non-residue, we have

Hence, ord(z) = 2ⁿ. Using similar reasoning, since a is a quadratic residue, b^2n-1 ≡ 1 (mod p), so ord(b)∣2^n-1. It follows that ord(b) < ord(z) = 2ⁿ (mod p).

Now, on each iteration, line 8 sets m = ord(b) and line 9 sets t = z^2k-m-1 , so

Line 10 sets z = t², so ord(z) = ord(t)∕2 = 2^m. After line 11, ord(b) < 2^m. This because the old value of b and the new value of z both have order 2^m. Hence, both of those numbers raised to the power 2^m-1 are -1, so their product (the new value of b) raised to that same power is (-1)² = 1. Line 13 sets k = m in preparation for the next iteration, and the loop invariant ord(b) < ord(z) = 2^k is maintained. Moreover, ord(b) is reduced at each iteration, so the loop must terminate after at most n iterations.

66 QR Probabilistic Cryptosystem

Let n = pq, p, q distinct odd primes. We can divide the numbers in Z*_n into four classes depending on their membership in QR_p and QR_q.⁴ Let Q_n¹¹ be those numbers that are quadratic residues mod both p and q; let Q_n¹⁰ be those numbers that are quadratic residues mod p but not mod q; let Q_n⁰¹ be those numbers that are quadratic residues mod q but not mod p; and let Q_n⁰⁰ be those numbers that are neither quadratic residues mod p nor mod q. Under these definitions, Q_n¹¹ = QR_n and Q_n⁰⁰ ∪ Q_n⁰¹ ∪ Q_n¹⁰ = QNR_n. Fact Given a Q_n⁰⁰ ∪Q_n¹¹, there is no known feasible algorithm for determining whether or not a QR_n that gives the correct answer significantly more than 1/2 the time.

The Goldwasser-Micali cryptosystem is based on this fact. The public key consist of a pair e = (n,y), where n = pq for distinct odd primes p, q, and y Q_n⁰⁰. The private key consists of p. The message space is = {0,1}.

To encrypt m , Alice chooses a random a QR_n. She does this by choosing a random member of Z*_n and squaring it. If m = 0, then c = a mod n. If m = 1, then c = ay mod n. The ciphertext is c.

It is easily shown that if m = 0, then c Q_n¹¹, and if m = 1, then c Q_n⁰⁰. One can also show that every a Q_n¹¹ is equally likely to be chosen as the ciphertext in case m = 0, and every a Q_n⁰⁰ is equally likely to be chosen as the ciphertext in case m = 1. Eve’s problem of determining whether c encrypts 0 or 1 is the same as the problem of distinguishing between membership in Q_n⁰⁰ and Q_n¹¹, which by the above fact is believed to be hard. Anyone knowing the private key p, however, can use the Euler Criterion to quickly determine whether or not c is a quadratic residue mod p and hence whether c Q_n¹¹ or c Q_n⁰⁰, thereby determining m.

67 Legendre Symbol

Let p be an odd prime, a an integer. The Legendre symbol is a number in {-1,0,+1}, defined as follows:

By the Euler Criterion (see Claim 2), we have

Theorem 1 Let p be an odd prime. Then

Note that this theorem holds even when p∣a.

The Legendre symbol satisfies the following multiplicative property: Fact Let p be an odd prime. Then

Not surprisingly, if a₁ and a₂ are both non-trivial quadratic residues, then so is a₁a₂. This shows that the fact is true for the case that

More surprising is the case when neither a₁ nor a₂ are quadratic residues, so

In this case, the above fact says that the product a₁a₂ is a quadratic residue since

Here’s a way to see this. Let g be a primitive root of p. Write a₁ ≡ g^k₁ (mod p) and a₂ ≡ g^k₂ (mod p). Since a₁ and a₂ are not quadratic residues, it must be the case that k₁ and k₂ are both odd; otherwise g^k₁∕2 would be a square root of a₁, or g^k₂∕2 would be a square root of a₂. But then k₁ + k₂ is even since the sum of any two odd numbers is always even. Hence, g^{(k₁+k₂)∕2} is a square root of a₁a₂ ≡ g^k₁+k₂ (mod p), so a₁a₂ is a quadratic residue.