An integer x ∈ ZN 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 y2 = x (modulo p), then (y − p)2 = x (modulo p), proving Proposition 13.2a ...