Square Roots

Let $p ∈ P$ be a prime number and $F_p$ its associated prime field. Then a number $x ∈ F_p$ is called a square root of another number $y ∈ F_p$, if $x$ is a solution to the following equation:

$$x^2 = y.$$

In this case, $y$ is called a quadratic residue. On the other hand, if $y$ is given and the quadratic equation has no solution $x$ , we call $y$ a quadratic non-residue.

For any $y ∈ F_p$, we denote the set of all square roots of $y$ in the prime field $F_p$ as follows:

$$\sqrt y = \{x \in F_p | x^2 = y\}.$$

If $y$ is a quadratic non-residue, then $\sqrt y = \empty$ (an empty set), and if $y = 0$, then $\sqrt y = \{0\}$. Moreover if $y \neq 0$ is a quadratic residue, then it has precisely two roots $\sqrt y = \{x, p − x\}$ for some $x ∈ F_p$. We adopt the convention to call the smaller one (when interpreted as an integer) the positive square root and the larger one the negative square root.

If $p ∈ P_{≥3}$ is an odd prime number with associated prime field $F_p$, then there are precisely $(p + 1)/2$ many quadratic residues and $(p − 1)/2$ quadratic non-residues.

Legendre symbol

In order to describe whether an element of a prime field is a square number or not, the so-called Legendre symbol can sometimes be found in the literature.

Let $p ∈ P$ be a prime number and $y ∈ F_p$ an element from the associated prime field. Then the Legendre symbol of $y$ is defined as follows:

$$\Big(\frac{y}{p}\Big) = \begin{cases} 1 \text{ if } y \text{ has square roots} \\ -1 \text{ if } y \text{ has no square roots} \\ 0 \text{ if } y = 0 \end{cases}$$

The Legendre symbol provides a criterion to decide whether or not an element from a prime field has a quadratic root or not. This, however, is not just of theoretical use: the so-called Euler criterion provides a compact way to actually compute the Legendre symbol. To see that, let $p ∈ P_{≥3}$ be an odd prime number and $y ∈ F_p$. Then the Legendre symbol can be computed as follows:

$$\Big(\frac{y}{p}\Big) = y^{\frac{p-1}{2}}$$