二次剩余

luckydrawbox · 2023-12-13 13:51:22 · 个人记录

先记几个结论：

• 若 n 是 p 的二次剩余，x^2\equiv n \pmod p 有两根，且两根互为相反数。
• 若 a^2-n 不是二次剩余，令 i^2=a^2-n\pmod p，那么 x^2\equiv n \pmod p 的其中一根为 (a+i)^{\frac{p+1}{2}}\mod p，即 (a+i)^{p+1}\equiv n\pmod p。

求解 x^2\equiv n\pmod p：

变量

函数

代码

ll ii,p;
ll get(ll n){
    return (((rand()<<16ll)%n+n+(rand()))%n+1);
}
struct xushu{
    ll a,b;
    xushu operator+(const xushu x)const{
        return (xushu){(a+x.a)%p,(b+x.b)%p};
    }
    xushu operator*(const xushu x)const{
        return (xushu){(a*x.a%p+ii*b%p*x.b%p)%p,(b*x.a%p+a*x.b%p)%p};
    }
}res;
ll qmi(ll a,ll b){
    ll ans=1;
    while(b){
        if(b&1)ans=ans*a%p;
        a=a*a%p;b>>=1;
    }
    return ans;
}
xushu qmi(xushu a,ll b){
    xushu ans;ans.a=1;ans.b=0;
    while(b){
        if(b&1)ans=ans*a;
        a=a*a;b>>=1;
    }
    return ans;
}
pair<ll,ll> Cipolla(ll n,ll pp){
    srand(time(0));
    ll a;p=pp;
    if(!n)return make_pair(0,0);
    if(qmi(n,(p-1)/2)!=1)return make_pair(-1,-1);
    do{
        a=get(p-1);
    }while(qmi((a*a%p-n%p+p)%p,(p-1)/2)==1);
    ii=(a*a%p-n%p+p)%p;
    res.a=a;res.b=1;
    res=qmi(res,(p+1)/2);
    ll ans1=res.a,ans2=p-res.a;
    if(ans1>ans2)swap(ans1,ans2);
    return make_pair(ans1,ans2);
}