Computer Security and Cryptography

13.5 QUADRATIC RESIDUES

An integer x ∈ Z_N is a quadratic residue of N if x has a square root modulo N; that is, if there exists a value that satisfies

The case of interest in cryptography is where N is the product of two prime numbers N = pq. The Chinese Remainder Theorem (Proposition 13.6) allows N = pq to be reduced to the study of each of the prime factors p and q of N. We now develop the theory in this special case N = p, a prime.

Proposition 13.2: If p is an odd prime:

13.2a	For every positive integer , the equation y2 − x = 0 (modulo p) has either 0 or 2 solutions.
13.2b	The set QUAD[p] of nonzero quadratic residues modulo p consists of the (p − 1)/2 integers in that are the values 12, 22, …, (p − 1/2)2 modulo p.
13.2c	x ∈ QUAD[p] if and only if .
13.2d	x ∉ QUAD[p] if and only if .

Proof: If y² = x (modulo p), then (y − p)² = x (modulo p), proving Proposition 13.2a ...