二次剩余 (Quadratic Residue)

只考虑奇质数 \(P\) 的情况

设求 \(x^2\equiv a\pmod P\) 的一个 \(x\)。

判断

由费马小定理 \(x^{P-1}\equiv 1 \pmod P\)，即 \(a^\frac{P-1}{2}\equiv 1 \pmod P\)。

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

---

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

原根法求二次剩余

先求出 \(P\) 的一个原根 \(g\)。

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

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

如果存在原根，那么 \(k\mod 2=0\)。

答案就是 \(g^{\frac{k}{2}}\mod P\)。

int BSGS(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;
}

---

更快的方法：Cipolla算法

要先找到一个数 \(y\)，满足不存在 \(\sqrt{y^2-a}\pmod P\)。

可以随机 \(y\)，期望可以两次找到这样的 \(y\)。

构造虚数 \(\omega = \sqrt{y^2-a}\)，那么答案就是 \(x=\sqrt{y^2-\omega^2}=\sqrt{(y+\omega)(y-\omega)}\)。

然后构造复数 \((\alpha,\beta)=\alpha+\beta\omega\)。

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

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

int Cipolla(int a,int k=0) {
	if(a<=1) return a;
	int x;
	while(1) {
		x=1ll*rand()*rand()%P;
		ll res=qpow((1ll*x*x-a+P)%P,(P-1)/2);
		if(res!=1) break;
	}
	ll w=(1ll*x*x-a+P)%P;
	int d=(P+1)/2;
	ll resx=1,resy=0;
	ll xx=x,yy=1;
	while(d) {
		if(d&1) {
			ll tx=(resx*xx+resy*yy%P*w)%P,ty=(resx*yy+resy*xx)%P;
			resx=tx,resy=ty;
            // 模拟复数乘法
		}
		ll tx=(xx*xx+yy*yy%P*w)%P,ty=2*xx*yy%P;
		xx=tx,yy=ty;
        // 模拟复数乘法
		d>>=1;
	}
	x=resx; // 答案就是实部
	if(k) x=min(x,(P-x)%P);
	return x;
}