O'Reilly logo

Computer Security and Cryptography by Alan G. Konheim

Stay ahead with the world's most comprehensive technology and business learning platform.

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

Start Free Trial

No credit card required

13.5 QUADRATIC RESIDUES

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 image that satisfies

image

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 image, the equation y2x = 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 image that are the values 12, 22, …, (p − 1/2)2 modulo p.
13.2c x QUAD[p] if and only if image.
13.2d x ∉ QUAD[p] if and only if image.

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.

Start Free Trial

No credit card required