解二次剩余
模板
大致证明
若有 \((a,p)=1\) 存在 x 使得 $$ x^2 \equiv n \ (\text{mod}\ p) $$ 则称 a 是 p 的二次剩余。
求 x 我们使用 Cipolla 算法，首先我们需要找到一个 r 使得 \(r^2-n\) 为二次非剩余，保证接下来的 \(w \in \mathbf{F}_{p^2}\) ，r 用随机数得到，再用 Euler 判别法，期望两次找到（二次剩余和二次非剩余分半）。
现在令我们的答案是 \(x \equiv (r+w)^{\frac{p+1}{2}} \ (\text{mod}\ p)\) （由后面 w 的性质构造得到），w 是类似于虚数的数，属于二次扩域 \(\mathbf{F}_{p^2}\) ，而 \(r \in \mathbf{F}_{p}\) ，这里我们希望（令） \(w^2 = r^2-n\) 使得 \((r+w)^2 \equiv n \ (\text{mod}\ p)\)。
\[\begin{aligned}
\therefore x^2 &\equiv (r+w)^{p+1} \equiv (r+w)^{p}(r+w) \\
&\equiv (r+w(w^2)^{\frac{p-1}{2}})(r+w) \equiv (r-w)(r+w) \\
&\equiv r^2-w^2 \equiv n \ (\text{mod}\ p)
\end{aligned}
\]
至此 \(x^2 \equiv n \ (\text{mod}\ p)\) 得证。
但还要证明此时的 \(x \in \mathbf{F}_{p}\)。令\(x=u+vw\)
\[\begin{aligned}
&\because (x^p)^2 \equiv (x^2)^p \equiv n^p \equiv n \equiv x^2 \ (\text{mod}\ p) \\
&\therefore x^p \equiv \pm x
\end{aligned}
\]
假设 \(x^p \equiv -x\)
\[\begin{aligned}
&\therefore (u+vw)^p \equiv -u-vw \\
&\equiv u^p+v^pw^p \equiv u-vw \\
&\therefore u=0 \ \text{原式不成立}
\end{aligned}
\]
当\(x^p \equiv x\)
\[\begin{aligned}
&\therefore (u+vw)^p \equiv u+vw \\
&\equiv u-vw \\
&\therefore v=0 \\
&\therefore x \in \mathbf{F}_{p}
\end{aligned}
\]
我也是闲的，在这写证明。。
直接上代码。
code
#include <bits/stdc++.h>
using namespace std;
#define int long long
mt19937 rnd(random_device{}());int n,p,ww=0;typedef struct fpp
{int u,v;// x=u+vwfpp()=default;fpp(int a,int b):u(a%p),v(b%p){}fpp operator*(const fpp &x) const{// (u+vw)*(a+bw)=ua+(v+b)ww + (ub+va)wreturn fpp(u*x.u%p+v*x.v%p*ww%p,v*x.u%p+u*x.v%p);}fpp operator^(int x) const{fpp base=*this;fpp ret(1,0);while(x){if(x&1){ret=ret*base;}base=base*base;x>>=1;}return ret;}
}fpp;int qpow(int base,int ci,int p)
{base%=p;int ret=1;while(ci){if(ci&1){ret=ret*base%p;}base=base*base%p;ci>>=1;}return ret;
}int cipolla(int n,int p)
{if(!n) return 0;if(qpow(n,(p-1)/2,p)==p-1) return -1;int r;while(1){// 找到r使得r^2-a为二次剩余--勒让德同余-1r=rnd()%p;if(qpow(((r*r-n)%p+p)%p, (p-1)/2, p)==p-1){break;}}// x=(r+w)^((p+1)/2)// w^2=r^2-nww=((r*r-n)%p+p)%p;auto ans=fpp(r,1)^((p+1)/2);// x=(r+1*w)^((p+1)/2)return ans.u;// x.v=0
}signed main()
{int T;scanf("%lld",&T);while(T--){scanf("%lld%lld",&n,&p);int ans=cipolla(n,p);if(ans==-1){printf("Hola!\n");}else{int ans2=(p-ans)%p;if(ans2<ans){swap(ans2,ans);}else if(ans==ans2){printf("%lld\n",ans);continue;}printf("%lld %lld\n",ans,ans2);}}return 0;
}