An integer *x* *∈* *Z _{N}* is a

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 y^{2} − 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 1^{2}, 2^{2}, …, (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*^{2} = *x* (modulo *p*), then (*y* − *p*)^{2} = *x* (modulo *p*), proving Proposition **13.2a ...**

Start Free Trial

No credit card required