概念
若 (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}) 个。
勒让德符号
[largeleft(frac{n}{p}
ight)=egin{cases}
1,\,&p
mid n ext{且}n ext{是}p ext{的二次剩余}\
-1,\,&p
mid n ext{且}n ext{不是}p ext{的二次剩余}\
0,\,&pmid n
end{cases}
]
由欧拉判别准则得：
[large left(frac{n}{p}
ight)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}})。
以上所有内容的证明在写了。