Quadratic Residue.
If there is an integer $0<x<p$ such that $x^2\equiv a\pmod{p}$. We call $a$ a quadratic residue modulo $p$. Otherwise (such $x$ doesn’t exist), we call $a$ a quadratic nonresidue modulo $p$.
Note that $p \nmid a$ to exclude the trivial cases $x=0$.
The quadratic residue problem requires us to solve the congrence $x^2\equiv a\pmod{p}$. Essentially it is to find the square root of $a$ in the sense of modulo $p$. Usually, the moduli $p$ is an odd prime.
Legendre Symbol
The legendre symbol is a number theoretic function $(\frac{a}{p})$ which is defined to be equal to $\pm 1$ depending on whether $a$ is a quadratic residue modulo $p$.
$$
(\frac{a}{p})=(a|p)=\begin{cases} \ 0, \ if \ \ p|a \\ \ 1, \ if \ a \ is \ a \ quadratic \ residue \ modulo \ p \\ -1 , \ if \ a \ is \ a \ quadratic \ nonresidue \ modulo \ p \end{cases}
$$
Euler’s Criterion
For an odd prime $p$ and $p \nmid a$, the Legendre symbol $(\frac{a}{p})\equiv a^{(p-1)/2} \pmod{p}$.
For an odd prime $p$ and $p \nmid a$, according to Euler’s critetion, we could determine whether $a$ is a quadratic residue modulo $p$ by checking whether $a^{(p-1)/2}\mod{p}$ equals to $1$ or not.
See the prove here.
虽然在本课程中关于二次剩余问题的内容只是浅尝辄止，但我觉得还是非常有必要将其单独拿出来进行介绍，因为这个问题的研究在数论上占有举足轻重的地位。
二次剩余问题本质上是模意义下的开根问题，实际上是 RSA 问题的铺垫：RSA 问题本质上是模意义下的开 $e$ 次根问题。因此，当 $e=2$ 时，RSA 问题与二次剩余问题等价。