欧拉准则
\(a\)是\(p\)的二次剩余等价于\(a^{\frac{p-1}{2}}\equiv 1\pmod p\)，\(a\)不是\(p\)的二次剩余等价于\(a^{\frac{p-1}{2}}\equiv -1\pmod p\)。
Cipolla
若\(a^2-n\)不是\(p\)的二次剩余，则\(p\)的二次剩余为\((a+\sqrt{a^2-n})^\frac{p+1}{2}\)。
因此我们随机\(a\)即可。\(\sqrt{a^2-n}\)的计算用复数。
时间复杂度约为\(O(\log^2p)\)。