class="markdown_views prism-tomorrow-night">

什么是二次剩余问题

就是求解形如$x^2equiv a ext{ } ( mod ext{ }p )$
的关于$x$的方程。 下面从不同的模数开始分类讨论解决二次剩余问题的方法

几个定义

如果关于$x$的方程
$x^2equiv a ext{ } ( mod ext{ }p )$有解。 称$a$是模$p$意义下的二次剩余，否则称为模$p$意义下的二次非剩余。 为什么会出现二次非剩余，其实很简单。 考虑在$\%p$意义下本质不同的数只会有$p$个。而其中$(-t)^2equiv t^2(mod ext{ }p)$，根据抽屉原理，总会有至少$O(frac{p}{2})$的数无法被$t^2\%p表示出来$ 勒让德符号（$Legendre ext{ }symbol$）:
$(frac{a}{p})=left{ egin{aligned} 1 &&&a是\%p下的二次剩余 \ -1 &&&a是\%p下的二次非剩余 \ 0 &&& aequiv0(mod ext{ }p) end{aligned} ight.$ 稍后会告诉怎么求勒让德符号。

1.模数为奇质数

首先来考虑$p$是奇质数的情况。

---

解的存在性问题

欧拉准则：

欧拉准则：$(frac{a}{p})equiv a^{frac{p-1}{2}}(mod ext{ }p)$ 当$p mid a$的时候欧拉准则显然成立。 否则由费马小定理我们有$a^{p-1}equiv 1（mod ext{ }p)$ 所以必然有$a^{frac{p-1}{2}}equiv pm1(mod ext{ }p)$ 先证明$(frac{a}{p})=1$的情况

必要性：

当$a$是$\%p$意义下的二次剩余，即$exist x,x^2equiv a(mod ext{ }p)$ 那么我们有$a^{frac{p-1}2}equiv (x^2)^{frac{p-1}2}equiv x^{p-1}equiv 1(mod ext{ }p)$ 必要性证明完毕

充分性：

设$p$有一个原根$g$，那么必然有$g^iequiv a(mod ext{ }p)$ 则：$g^{frac{i(p-1)}2}equiv 1(mod ext{ }p)$ 由于$g$为原根，所以必然会有$(p-1)midfrac{i(p-1)}{2}$ 即$i$是偶数。 必然存在解$x_0equiv g^{frac{i}2}(mod ext{ }p)$ 充分性证毕。 那么$(frac{a}p)equiv-1(mod ext{ }p)$的情况也就十分显然了。 首先由费马小定理$a^{frac{p-1}{2}}equiv pm 1(mod ext{ }p)$ 由于前面的欧拉准则在$(frac{a}{p})=1$的必要性，二次非剩余的情况下$x^2equiv a^{p-1}equiv -1(mod ext{ }p)$，显然不可能，违反了费马小定理。

---

求解：

$O(log^2 p)$解法：

首先求出$p-1=2^ts$