31-4 Quadratic residues

Let $p$ be an odd prime. A number $a \in Z_p^*$ is a quadratic residue if the equation $x^2 = a \pmod p$ has a solution for the unknown $x$.

a. Show that there are exactly $(p - 1) / 2$ quadratic residues, modulo $p$.

b. If $p$ is prime, we define the Legendre symbol $(\frac{a}{p})$, for $a \in \mathbb Z_p^*$, to be $1$ if $a$ is a quadratic residue modulo $p$ and $-1$ otherwise. Prove that if $a \in \mathbb Z_p^*$, then

$$\left(\frac{a}{p}\right) \equiv a^{(p - 1) / 2} \pmod p.$$

Give an efficient algorithm that determines whether a given number $a$ is a quadratic residue modulo $p$. Analyze the efficiency of your algorithm.

c. Prove that if $p$ is a prime of the form $4k + 3$ and $a$ is a quadratic residue in $\mathbb Z_b^*$, then $a^{k + 1} \mod p$ is a square root of $a$, modulo $p$. How much time is required to find the square root of a quadratic residue $a$ modulo $p$?

d. Describe an efficient randomized algorithm for finding a nonquadratic residue, modulo an arbitrary prime $p$, that is, a member of $\mathbb Z_p^*$ that is not a quadratic residue. How many arithmetic operations does your algorithm require on average?

(Omit!)