模素数

解 $$x^{2}\equiv a \ \mathrm{mod},p$$

解的存在性

求 Legendre 符号 $\left( \frac{a}{p} \right)$

求解

• 若 $p\equiv 3 \ \mathrm{mod},4$ 则 $x\equiv \pm n^{\frac{p+1}{4}}$
• 若 $p\equiv 1 \ \mathrm{mod},4$ 则 试根

模素数幂

解 $$x^{2}\equiv a \ \mathrm{mod},p^{k}$$ 先求 模素数 的一次幂解 $x_{0}$，再用 Hensel 引理 逐级抬升到 $\mathrm{mod},p^{k}$

模合数

解 $$x^{2}\equiv a \ \mathrm{mod},(p_{1}^{k_{1}}\dots p_{n}^{k_{n}})$$ 对每个 $\mathrm{mod},p_{i}^{k_{i}}$ 求解，再用 中国剩余定理 CRT 整合解