概念
若 \(n\) 不是 \(p\) 的倍数且在模 \(p\) 的意义下和某个数的平方同余，则称 \(n\) 为模 \(p\) 的二次剩余，否则称 \(n\) 为模 \(p\) 的非二次剩余。
求解二次剩余就是求解形如：
\[\large x^2 \equiv n \pmod{p}
\]
的方程。只考虑 \(p\) 为奇素数的情况。
解的数量
不考虑 \(0\)，模 \(p\) 的二次剩余有 \(\frac{p-1}{2}\) 个，非二次剩余有 \(\frac{p-1}{2}\) 个。
勒让德符号
\[\large\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}
\]
由欧拉判别准则得：
\[\large \left(\frac{n}{p}\right)\equiv n^{\frac{p-1}{2}}\pmod p
\]
Cipolla 算法
找到一个数 \(a\) 满足 \(a^2-n\) 是非二次剩余，随机找即可，因为非二次剩余有 \(\frac{p-1}{2}\) 个，期望 \(2\) 次即可找到。
设虚数单位 \(i=\sqrt{a^2-n}\)，得 \(x^2 \equiv n \pmod{p}\) 的解为 \((a+i)^{\frac{p+1}{2}}\)。
以上所有内容的证明在写了。