前言

之前遇到过一些关于二次剩余的题目，因为姿势不够都跳了。由于最近觉得自己的数论姿势严重不足，便觉得有必要来学习一下二次剩余相关的算法。
学完后感觉这个算法作者的脑洞真的是比较大，居然能想出这么巧妙的构造。
关于这个算法的介绍，我比较推荐czy大爷的博文。

前置技能

（以下内容均在模数p为奇素数的前提下讨论）

二次剩余

首先要搞懂什么是二次剩余。若方程x2≡a(modp)有解，则称a为p的二次剩余，反之则称a为p的二次非剩余。说白了就是在模意义下能否开根号。

勒让德符号

勒让德符号是这样定义的：
(ap)=⎧⎩⎨1,−1,0,a为p的二次剩余a为p的二次非剩余a≡0(modp)

欧拉判别法

若a是不被p整除的正整数，则(ap)≡ap−12
证明： 当(ap)=1时，方程x2≡a(modp)有解。根据费马小定理可得ap−12≡1(modp)。 当(ap)=−1时，方程x2≡a(modp)无解。因为p是素数，由数论知识可知对于每个1<=i<p使得ij≡a(modp)。所以我们可以把1,2,...,p−1分成p−12对，使得每对的乘积都为a。
于是有(p−1)!≡ap−12。根据威尔逊定理有(p−1)!≡−1(modp)，可得ap−12≡−1(modp)。

定理1

定理1：对于方程x2≡a(modp)，总共有p−12个不同的n使得该方程有解。
证明：若有两个数u和v均满足它们的平方在模p意义下同余，那么必然有p|(u