二次剩余-学习笔记

二次剩余是干什么的？简单的说就是模意义下开根号：$x^2=n \mod p$ ### P为2的情况 解为$x=1$ ## P为奇素数的情况 **勒让德符号**：  如何求值？ **定理**：$\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}\pmod p$ 证明： 当a在模p意义下是二次剩余时，令$x^2=a \mod p$，那么就有$x^{p-1}=1 \mod p$，由费马小定理，显然x存在。 当a在模p意义下不是二次剩余时，依旧令$x^2=a \mod p$，那么就有$x^{p-1}=-1 \mod p$，由费马小定理，显然x不存在。 当$a=0 \mod p$时显然满足。 **因此首先判断有解：$n^{\frac{p-1}{2}} =1 \mod p$** **然后找到一个a，使得$w=a^2-n$是p的非二次剩余，答案为$(a+\sqrt{w})^{p+1/2}$** 证明： 首先证明$(a+b)^p=a^p+b^p \mod p$： $(a+b)^n\equiv\sum_{i=0}^nC_n^ia^ib^{n-i}\pmod n$ 由于n是质数，因此当i不等于0且不等于n的时候，组合数阶乘公式中的n是没有办法被消掉的，就会被模成0，因此这些项都是对答案没有贡献的。而i=0或i=n时，我们就分别可以得到$ a^n$和$b^n$，定理得证。  如何求$a+\sqrt{w}$，不是w没有二次剩余吗？ 就像$\sqrt{-1}$一样，我们将$\sqrt{w}$看作类似$i$的存在，然后定义模意义下复数的乘法，然后快速幂即可。 如何保证最终快速幂的结果虚部为0？ 根据拉格朗日定理，我们知道在任意一个模$p(p\in\mathbb P)$的数域里面，任意一个多项式$f(x)$最多有$deg(f(x))$个根（$f(x)\equiv0\pmod p$的解称为f(x)在$\mathbb F_p$下的根），$deg$表示多项式的度数，即最大指数。由于$\mathbb F_{p^2}$是对$\mathbb F_p$域的扩充，$\mathbb F_p$域的两根一定在$\mathbb F_{p^2}$内也有效，并且我们知道$x^2-n$在数域$\mathbb F_p$下的根有两个（$x1,x2$），那么$x1,x2$一定也是$\mathbb F_{p^2}$域下的根，也就是“虚部”系数为0。 由此问题完美解决，算法时间复杂度是$O(\log p)$的。 还有一个问题如何找到a？方法是随机！因为概率大概是$0.5$ ```cpp struct F { int x,y; F() {} F(const int &xx,const int &yy) { x=xx,y=yy; } friend F operator*(const F &a,const F &b) { return F(((LL)a.x*b.x%md+(LL)a.y*b.y%md*w%md)%md,((LL)a.x*b.y%md+(LL)a.y*b.x%md)%md); } }; F qpow(F a,int b) { F res(1,0); for(; b; b>>=1,a=a*a) if(b&1) res=res*a; return res; } int qpow(int a,int b) { int res=1; for(; b; b>>=1,a=(LL)a*a%md) if(b&1) res=(LL)res*a%md; return res; } int solve(int n) { if(md==2) return 1; if(qpow(n,(md-1)/2)==md-1) return -1; while(1) { int a=rand()%md; w=((LL)a*a%md-n+md)%md; if(qpow(w,(md-1)/2)==md-1) { F ans=qpow(F(a,1),(md+1)/2); return ans.x; } } } ``` ## P为奇素数的幂 [Blog](https://blog.csdn.net/acdreamers/article/details/10182281) ### N次剩余 借助离散对数。 [Blog](https://blog.csdn.net/qq_27599517/article/details/52914733)