二次剩余(懒人模板总结)

只考虑奇质数的情况

设求$\sqrt a \pmod P$

Part1 判断

存在二次剩余即$a^{\frac{(P-1)} {2} }=1 \pmod P$

---

(对于所有$a=0,1$的情况需要特判)

Part2 原根法求二次剩余

先求出$P$的一个原根$g$

那么可以用$g^k$表示出$[1,P-1]$的所有数

用$BSGS$可以在$O(\sqrt n\log n)$的时间内求出$a=g^k$

如果存在原根，那么$k\mod 2=0$

答案就是$g^{\frac{k} {2} }\mod P$

int Quad(int a,int k=0) {
	if(a<=1) return a;    
    int g=Getg(P);
	static map <int,int> M;
	int S=sqrt(P-1);
	for(int i=0,t=1;i<S;++i,t=1ll*t*g%P) M[t]=i;
	int res=0;
	int w=qpow(g,S);
	for(int i=0,t=1;i<P-1;i+=S,t=1ll*t*w%P) {
		ll x=1ll*a*qpow(t,P-2)%P;
		if(M.count(x)) {
			res=M[x]+i;
			break;
		}
	}
	res=qpow(g,res/2);
	if(k) res=min(res,(P-res)%P);
	return res;
}

---

Part3 更快的方法

要先找到一个数$x$，满足不存在$\sqrt{x^2-a}\pmod P$

可以随机$x$，期望可以在$O(1)$时间内找到这样的$x$

然后构造复数$(\alpha,\beta)=\alpha+\sqrt{x^2-a}\beta$

求出$(x,1)^{\frac{(P+1)} {2} }$，模拟复数乘法即可

可以证明结果没有虚部，就是答案

int Quad(int a,int k=0) {
	if(a<=1) return a;
	ll x;
	while(1) {
		x=1ll*rand()*rand()%P;
		if(qpow((x*x-a+P)%P,(P-1)/2)!=1) break;
	}
	ll w=(x*x-a+P)%P;
	Pii res=mp(1,0),t=mp(x,1);
	auto Mul=[&](Pii a,Pii b){ // 复数乘法
		int x=(1ll*a.first*b.first+1ll*a.second*b.second%P*w)%P;
		int y=(1ll*a.first*b.second+1ll*a.second*b.first)%P;
		return mp(x,y);
	};
	int d=(P+1)/2;
	while(d) {
		if(d&1) res=Mul(res,t);
		t=Mul(t,t);
		d>>=1;
	}
	ll r=(res.first%P+P)%P;
	if(k) r=min(r,(P-r)%P);
	return r;
}