二次剩余小记

**P.S** 本文只探讨模数$p$是**奇质数**的情况。 ## 目标/定义 求解 $\large{x^2=c(mod\ p)}$ 这个方程组。 如果方程有解,则称$c$是模$p$的**二次剩余**,否则称作二次非剩余。 (下面默认在模$p$的剩余系下讨论) ## 欧拉判别法 给定$c,p$,如何判定 $x^2=c$ 是否有解呢? $\color{blue}\text{结论:}$ $c^{\large{\frac{p-1}{2}}}=\begin{cases}\ \ \ 1\rightarrow\text{有解}\\ -1\rightarrow\text{无解}\end{cases}$ $\color{blue}\text{证明:}$ - 引理$\color{blue}1.1$ : $c^{\large{\frac{p-1}{2}}}=±1$ 由费马小定理得$(c^{\large{\frac{p-1}{2}}})^2=c^{p-1}=1$,可得$c^{\large{\frac{p-1}{2}}}=±1$ - 引理$\color{blue}1.2$ $c^{\large{\frac{p-1}{2}}}=-1 \Rightarrow c$不是二次剩余 采用反证法,假设有$x^2=c$,可得$c^{\large{\frac{p-1}{2}}}=x^{p-1}=-1$ 与费马小定理矛盾,原命题得证。 - 引理$\color{blue}1.3$ $c^{\large{\frac{p-1}{2}}}=-1 \Leftarrow c$不是二次剩余 假设有$x^2=c$,但是$x$不是同余系里面的数,可以视为虚数,只满足$x^2=c$这一条性质。 由于$x$不是同余系内的数,**必定**不满足费马小定理,可得$x^{p-1}≠1$,那么只能是$-1$了。 (费马小定理对且只对同余系生效) 综上三个引理可以逻辑推导出欧拉判别法,证毕。 ## 二次剩余的个数 $\color{blue}\text{结论:}$ 模$p$下的二次剩余恰有$\dfrac{p-1}{2}$个。 - 引理 : $c^2=(p-c)^2$ 显然成立,由此可得,如果$x^2=c$有解,则必然有两解。 $\color{blue}\text{证明:}$ 任选两个数$x,y(x≠y)$,且$x^2=y^2$ 那么$(x+y)(x-y)=0$,即$p|(x+y)(x-y)$, 显然$p|(x-y)$不成立,那么$p|(x+y)$,即$x+y=0$。 那么,对于一个$x$,和它平方相同的有且仅有另外一个$y$。 总共有$\dfrac{p-1}{2}$个不同的平方,那么二次剩余,二次非剩余各有$\dfrac{p-1}{2}$个。 ## Cipolla算法 现在真正来求解$x^2=c(mod\ p)$ 首先判定方程是否无解(如果$c=0$则输出0) 如果有解,我们任意找一个$a$,使得$a^2-c$是**二次非剩余**。 方法:不断随机然后判定。根据上文内容,期望随机次数$2$次。 设$w^2=(a^2-c)$,注意$w$不是同余系里面的数,可以理解为虚数,只有$w^2=(a^2-c)$这一条性质。 我们扩系,把每个数变成$a+bw$的形式,重载运算。容易证明扩系之后仍然是环。 > **P.S** 设$s=w^2=(a^2-c)$ > $(x_1+y_1w)*(x_2+y_2w)=(x_1x_2+y_1y_2s)+(x_1y_2+x_2y_1)w$ 那么$c=(a+w)^{p+1}$,所以$x=(a+w)^{\frac{p+1}{2}}$ - 引理$\color{blue}3.1$ $(a+b)^p=a^p+b^p$ 二项式展开可得 : $(a+b)^p=\sum\limits_{i=0}^p\dbinom{i}{p}a^{i}b^{p-i}$ 由卢卡斯定理 : $\dbinom{i}{p}=\dbinom{i/p}{p/p}\dbinom{i\%p}{p\%p}=\dbinom{i/p}{1}\dbinom{i\%p}{0}$ 这个式子只在$i=0$或者$p$的时候值为1,否则为0. 所以$(a+b)^p=a^p+b^p$ - 引理$\color{blue}3.2$ $w^p=-w$ $w^p=w^{p-1}w=(a^2-c)^{\large{\frac{p-1}{2}}}w$ 由欧拉判别法,$(a^2-c)^{\large{\frac{p-1}{2}}}=-1$,证毕。 那么 : $(a+w)^{p+1}=(a^p+w^p)(a+w)=(a+w)(a-w)$ $=a^2-w^2=a^2-a^2+c=c$ 正确性得证。 [P5491 【模板】二次剩余](https://www.luogu.org/problem/P5491) ```cpp #include<algorithm> #include<cstdio> #define ll long long using namespace std; int mod,c; ll powM(ll a,int t) { ll ans=1; while(t){ if (t&1)ans=ans*a%mod; a=a*a%mod; t>>=1; }return ans; } ll sav; struct Mcp { ll x,y; Mcp operator * (Mcp const& B) const {return (Mcp){(x*B.x+y*B.y%mod*sav)%mod,(x*B.y+y*B.x)%mod};} }; Mcp powM(Mcp a,int t) { Mcp ans=(Mcp){1,0}; while(t){ if (t&1)ans=ans*a; a=a*a; t>>=1; }return ans; } void solve() { scanf("%d%d",&c,&mod); if (c==0) {puts("0");return ;} if (powM(c,(mod-1)/2)==mod-1) {puts("Hola!");return ;} int a; while(1){ a=(rand()%(mod-1)+mod)%(mod-1)+1; sav=(1ll*a*a-c+mod)%mod; if (powM(sav,(mod-1)/2)==mod-1){ Mcp W=(Mcp){a,1}; W=powM(W,(mod+1)/2); ll x1=W.x,x2=mod-W.x; if (x1>x2)swap(x1,x2); printf("%lld %lld\n",x1,x2); break; } } } int main() { int T; scanf("%d",&T); while(T--)solve(); return 0; } ```