## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

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 (yp)2 = x (modulo p), proving Proposition 13.2a ...

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required