二次剩余 — Lalande.

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.

Eureka moment!

虽然在本课程中关于二次剩余问题的内容只是浅尝辄止，但我觉得还是非常有必要将其单独拿出来进行介绍，因为这个问题的研究在数论上占有举足轻重的地位。

二次剩余问题本质上是模意义下的开根问题，实际上是 RSA 问题的铺垫：RSA 问题本质上是模意义下的开 $e$ 次根问题。因此，当 $e=2$ 时，RSA 问题与二次剩余问题等价。