Chapter 31, Problem 4P

a.

Program Plan Intro

To show that there are exactly $\frac{\left(p-1\right)}{2}$ quadratic residues, modulo p .

b.

Program Plan Intro

To give the efficient algorithm that determines whether a given number $a$ is a quadratic residue modulo p . Analyze the efficiency of algorithm.

c.

Program Plan Intro

To prove that a is a quadratic residue in $Z^{*}{}_p$ , then $a^{k+1}\mathrm{mod}p$ is a square root of a , modulo p if p is a prime of the form

d.

Program Plan Intro

To describe an efficient randomized algorithm for finding a nonquadratic residue and also find the number of arithmetic operations that algorithm will require on an average.