二次剩余学习笔记
定义
求解方程 \(x^2 \equiv n(mod\ p)\)
保证 \(p\) 是奇素数
欧拉准则
用来判断一个数 \(n\) 是否为二次剩余
根据费马小定理，有 \(n^{p-1} \equiv1(mod\ p)\)
因为 \(p\) 为奇素数
所以 \(n^{2\frac{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^{2\frac{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}}\) 就是我们想要的一组解
它的相反数就是另一组解
可以证明得出来的解是没有虚部的
代码
#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\n");
continue;
}
rg int haha=solve();
if(haha==-1){
printf("Hola!\n");
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\n",ans1);
else printf("%d %d\n",ans1,ans2);
}
return 0;
}