class="markdown_views prism-atom-one-light"> 在学多项式求逆的时候顺便就推了一下多项式的开根，
结果毫无疑问的要用到二c次剩余，顺路就学了一下，

二次剩余

给出$n,P$(P为奇质数)，如果存在一个 $a$ 使得 $a^2equiv n pmod{P}$ ，那么n在模P的意义下就是二次剩余，

CTY大佬的方法

因为这个问题是由二次开方引起的，自然，模数有已知原根$r$，那么：
$r^{2Ind_r(a)}equiv r^{Ind_r(n)} pmod{P}$

$Ind$是离散对数里面的东西，定义为$r^{Ind_r(x)}equiv x pmod{P}$

• 定理1：方程 $a^2equiv n pmod{P}$，只有$frac{P-1}{2}$个n使方程有解（0除外）
• 证明：可以发现，如果$Ind_r(n)$为奇数的话，这个方程就无解，因为$Ind_r(n)$相当于是在模P-1的意义下的，而P-1必为偶数，也就是不存在2的逆元；$Ind_r(n)$的取值范围为0~P-2，共有$frac{p-1}{2}$为偶数，所以只有这么多个n使方程有解。

回归主题，要求出$Ind_r(a)$，也就是要求出$Ind_r(n)$， 那么如何快速求出$Ind_r(n)$呢？
设一个阈值$omega$，那么$Ind_r(n)$一定可以被表示成$aomega+b$，
也就是：
$r^{aomega}*r^{b}equiv n pmod{P}$
$r^{b}equiv n*(r^{aomega})^{-1} pmod{P}$
显然，所有的$r^b$可以预处理出来，
那么，剩下的只要枚举a了，判断是否有对应的b即可，
如果$omega=sqrt{n}$，复杂度即为：$O(sqrt{n}log(n))$（还有求逆元） . 对于上面的定理1，其实还有一种证明：

• 定理1：方程 $a^2equiv n pmod{P}$，只有$frac{P-1}{2}$个n使方程有解（0除外）
• 证明：考虑对于所有的a，可以平方出多少个不同的n，
  如果两个数$a,b$他们满足$a^2equiv b^2 pmod{P}$，那么$a^2-b^2equiv 0 pmod{P}$也就是$(a^2-b^2)|P$，$(a-b)(a+b)|P$，显然(a-b)不可能是P的倍数，所以(a+b)就肯定是P的倍数，也就是a,b也满足：$a+b=P$，
  所以能组合出的不同的n就只有$frac{P-1}{2}$个

---

Cipolla

介绍一个东西：勒让德符号(Legendre symbol) 定义为：$left(frac{n}{P} ight)=egin{cases} 1& ext{n在模P意义下是二次剩余}\ -1& ext{n在模P意义下是非二次剩余}\ 0,&nequiv0pmod{P} end{cases}$ 求值也很简单：（当然你用上边的方法判定没人拦…）

• 定理2：$left(frac{n}{P} ight)equiv n^{frac{P-1}{2}} pmod{P}$
• 证明：先证明$n^{frac{P-1}{2}}$