二次剩余
一个数 $a$，如果不是 $p$ 的倍数且模 $p$ 同余于某个数的平方，则称 $a$ 为模 $p$ 的 二次剩余。而一个不是 $p$ 的倍数的数 $b$，不同余于任何数的平方，则称 $b$ 为模 $p$ 的 二次非剩余。
对二次剩余求解，也就是对常数 $a$ 解下面的这个方程： $$ x^2\equiv a\pmod p $$ 通俗一些，可以认为是求模意义下的开方。这里只讨论 $p$ 为奇素数 的求解方法，将会使用 Cipolla 算法。
解的数量
对于 $x^2\equiv n\pmod p$，能满足 “$n$ 是模 $p$ 的二次剩余” 的 $n$ 一共有 $\frac{p-1}{2}$ 个（$0$ 不包括在内），二次非剩余有 $\frac{p-1}{2}$ 个。
对于给定的 $n$ 和 $p$，若 $n$ 是 $p$ 的二次剩余，则关于 $x$ 的方程 $x^2\equiv n\pmod p$ 有且仅有两个解 $\pm x_0$ 满足 $x_0^2\equiv n\pmod p$。
勒让德符号
$$ \left(\frac n p\right)=\begin{cases}1,\,&p\nmid n\text{且}n\text{是}p\text{的二次剩余}\\ -1,\,&p\nmid n \text{且}n\text{不是}p\text{的二次剩余}\\ 0,\,&p\mid n\end{cases} $$
欧拉判别准则
$$ \left(\frac n p\right)\equiv n^{\frac{p-1}{2}}\pmod p $$
$n$ 是二次剩余，当且仅当 $n^{\frac{p-1}{2}}\equiv 1\pmod p$。
$n$ 是二次非剩余，当且仅当 $n^{\frac{p-1}{2}}\equiv -1\pmod p$。
Cipolla 算法
找到一个数 $a$ 满足 $a^2-n$ 是 二次非剩余，至于为什么要找满足二次非剩余的数，在下文会给出解释。这里通过生成随机数再检验的方法来实现，由于二次非剩余的数量为 $\frac{p-1}{2}$，接近 $\frac p 2$，所以期望约 $2$ 次就可以找到这个数。
建立一个“复数域”，并不是实际意义上的复数域，而是根据复数域的概念建立的一个类似的域。在复数中 $i^2=-1$，这里定义 $i^2=a^2-n$ ，于是就可以将所有的数表达为 $A+Bi$ 的形式，这里的 $A$ 和 $B$ 都是模意义下的数，类似复数中的实部和虚部。
在有了 $i$ 和 $a$ 后可以直接得到答案， $x^2\equiv n\pmod p$ 的解为 $(a+i)^{\frac{p+1}2}$。
参考实现：
