二次剩余学习笔记

定义

求解方程 (x^2 equiv n(mod p))

保证 (p) 是奇素数

欧拉准则

用来判断一个数 (n) 是否为二次剩余

根据费马小定理，有 (n^{p-1} equiv1(mod p))

因为 (p) 为奇素数

所以 (n^{2frac{p-1}{2}} equiv1(mod p))

所以 (n^{frac{p-1}{2}}) 是 (1) 开根后的结果，它的值只能等于等于 (1) 或 (p-1)

若 (n) 为二次剩余，则 (n equiv x^2(mod p))

所以 (n^{frac{p-1}{2}} equiv x^{p-1} equiv 1 (mod p))

因此可以认为 (n^{frac{p-1}{2}} equiv 1(mod p))等价于 (n) 是二次剩余

(n^{frac{p-1}{2}} equiv p-1(mod p)) 等价于 (n) 是非二次剩余

求解

找到一个数 (a) 使得 (a^2-n) 是非二次剩余

我们可以随机寻找，每次都有 (frac{1}{2}) 的概率寻找成功

接下来定义 (i^2 equiv a^2-n(mod p))

因为 (a^2-n) 是非二次剩余，所以 (i) 用实数是无法表示出来的

但是我们可以像虚数那样定义一个 (i)

将所有的数都表示为 (A+Bi) 的形式

此时就有 (i^p=ii^{2frac{p-1}{2}}=i(a^2-n)^{frac{p-1}{2}}=-i)

((a+i)^{p+1} equiv (a^p+i^p)(a+i) equiv (a-i)(a+i) equiv a^2-i^2 equiv n (mod p))

((a+i)^p) 在进行二项式展开时除了第一项和最后一项分子的位置都会有一个 (p) 没有消去，在模意义下就变成了 (0)

那么 ((a+i)^{frac{p+1}{2}}) 就是我们想要的一组解

它的相反数就是另一组解

可以证明得出来的解是没有虚部的

代码

P5491 【模板】二次剩余

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#define rg register
inline int read(){
	rg int x=0,fh=1;
	rg char ch=getchar();
	while(ch<'0' || ch>'9'){
		if(ch=='-') fh=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*fh;
}
int t,n,p,w,now;
long long mulmod(rg long long now1,rg int now2){
	return now1*=now2,now1>=p?now1%p:now1;
}
int delmod(rg int now1,rg int now2){
	return now1-=now2,now1<0?now1+p:now1;
}
int addmod(rg int now1,rg int now2){
	return now1+=now2,now1>=p?now1-p:now1;
}
struct fs{
	int x,y;
	fs(){}
	fs(rg int aa,rg int bb){
		x=aa,y=bb;
	}
	friend fs operator *(const fs& A,const fs& B){
		return fs(addmod(mulmod(A.x,B.x),mulmod(w,mulmod(A.y,B.y))),addmod(mulmod(A.x,B.y),mulmod(A.y,B.x)));
	}
};
int ksm1(rg int ds,rg int zs){
	rg int nans=1;
	while(zs){
		if(zs&1) nans=mulmod(nans,ds);
		ds=mulmod(ds,ds);
		zs>>=1;
	}
	return nans;
}
int ksm2(rg fs ds,rg int zs){
	rg fs nans=fs(1,0);
	while(zs){
		if(zs&1) nans=nans*ds;
		ds=ds*ds;
		zs>>=1;
	}
	return nans.x;
}
int solve(){
	n%=p;
	if(ksm1(n,(p-1)/2)==p-1) return -1;
	while(1){
		now=rand()%p+1;
		w=mulmod(now,now);
		w=delmod(w,n);
		if(ksm1(w,(p-1)/2)==p-1) break;
	}
	return 1;
}
int main(){
	srand(time(0));
	t=read();
	while(t--){
		n=read(),p=read();
		if(n==0){
			printf("0
");
			continue;
		}
		rg int haha=solve();
		if(haha==-1){
			printf("Hola!
");
			continue;
		}
		rg int ans1=ksm2(fs(now,1),(p+1)/2);
		rg int ans2=p-ans1;
		if(ans1>ans2) std::swap(ans1,ans2);
		if(ans1==ans2) printf("%d
",ans1);
		else printf("%d %d
",ans1,ans2);
	}
	return 0;
}