二次剩余学习笔记
yangmingshuo114514
·
·
算法·理论
前置知识
复数
同余
费马小定理
二项式定理
原根
二次剩余
P5491 【模板】二次剩余
题意
给定 N,p，解 x^2\equiv N(\bmod\ p) 这么一个方程。现只考虑 p 是奇素数，N\not\equiv0(\bmod\ p)。
定义
### 性质
1. 二次剩余的乘积也为二次剩余。
若 $N,M$ 为模 $p$ 意义下的二次剩余，则存在整数 $x,y$ 使得 $x^2\equiv N(\bmod\ p),y^2\equiv M(\bmod\ p)$，则必然有 $NM\equiv x^2y^2=(xy)^2$，故 $NM$ 也为模 $p$ 意义下的二次剩余。
2. 二次剩余的逆元也为二次剩余。
若 $N$ 为模 $p$ 意义下的二次剩余，则存在整数 $x$ 使得 $x^2\equiv N(\bmod\ p)$，则必然有 $N^{-1}\equiv x^{-2}=(x^{-1})^2$，故 $N^{-1}$ 也为模 $p$ 意义下的二次剩余。
### 解的个数
设 $x^2\equiv N(\bmod\ p)$ 有两个解分别为 $x_1,x_2$，且 $0\le x_1<x_2<p$，则 $x_1^2\equiv x_2^2(\bmod\ p)$，移项，得 $x_2^2-x_1^2\equiv0(\bmod\ p)$，再运用平方差公式，得 $(x_2-x_1)(x_2+x_1)\equiv0(\bmod\ p)$。由于 $0\le x_1<x_2<p$，所以有 $0<x_2-x_1<p$，有 $x_2-x_1\not\equiv0(\bmod\ p)$。根据 $p|(x_2-x_1)(x_2+x_1)$ 和 $p\not|x_2-x_1$，只能有 $p|x_2+x_1$。即 $x_1+x_2=p$。故方程在模 $p$ 意义下只能有两个解，且两个解在模 $p$ 意义下两解互为相反数。
### 二次剩余分布
由上文得，一个二次剩余对应 $2$ 个解，不难得到在 $1\sim p-1$ 里二次剩余和二次非剩余各占一半，即二次剩余和二次非剩余各有 $\frac{p-1}{2}$ 个。
### 欧拉准则
$$
N^{\frac{p-1}{2}}\equiv\begin{cases}
1(\bmod\ p)&(\exist x\in\Bbb{Z}),N\equiv x^2(\bmod\ p)\\
-1(\bmod\ p)&\text{otherwise}
\end{cases}
$$
即当 $N$ 是模 $p$ 的二次剩余时，$N^{\frac{p-1}{2}}\equiv1(\bmod\ p)$。当 $N$ 是模 $p$ 的二次剩余时，$N^{\frac{p-1}{2}}\equiv-1(\bmod\ p)$。
考虑如何证明。
首先根据费马小定理，有 $N^{p-1}\equiv1(\bmod\ p)$，移项，得 $N^{p-1}-1\equiv0(\bmod\ p)$，套个平方差，得 $(N^{\frac{p-1}{2}}-1)(N^{\frac{p-1}{2}}+1)\equiv0(\bmod\ p)$。由于 $p$ 是奇素数，$p\ge3$，而 $(N^{\frac{p-1}{2}}+1)-(N^{\frac{p-1}{2}}-1)=2<3$，所以只能有 $p|N^{\frac{p-1}{2}}-1$ 或 $p|N^{\frac{p-1}{2}}+1$，即只能有 $N^{\frac{p-1}{2}}\equiv1(\bmod\ p)$ 或 $N^{\frac{p-1}{2}}\equiv-1(\bmod\ p)$。
然后考虑证明：$N$ 为二次剩余 $\Leftrightarrow$ $N^{\frac{p-1}{2}}\equiv1(\bmod\ p)$，即二者可以互推，互为充要条件。
若 $N$ 为二次剩余，则根据定义，$\exist x\in\Bbb{Z},x^2\equiv N(\bmod\ p)$。则 $N^{\frac{p-1}{2}}\equiv(x^2)^{\frac{p-1}{2}}=x^{p-1}$，又根据费马小定理 $x^{p-1}\equiv1(\bmod\ p)$，则 $N^{\frac{p-1}{2}}\equiv1(\bmod\ p)$。
若 $N^{\frac{p-1}{2}}\equiv1(\bmod\ p)$，设 $g$ 为模 $p$ 意义下的原根，由于原根满足 $g^k\bmod p$ 在 $k$ 取遍 $1\sim p-1$ 时互不相同，又因为 $N\not\equiv0(\bmod\ p)$，则必然可以找到那么一个 $k$，满足 $N\equiv g^k(\bmod\ p)$。则有 $(g^k)^{\frac{p-1}{2}}\equiv1(\bmod\ p)$。根据原根的性质，满足 $g^x\equiv1(\bmod\ p)$ 的整数 $x$ 必然满足 $p-1|x$，则有 $p-1|k\frac{p-1}{2}$，则必有 $k$ 为偶数。此时令 $x\equiv g^{\frac{k}{2}}$，则有 $x^2\equiv(g^{\frac{k}{2}})^2= g^k\equiv N(\bmod\ p)$，则 $N$ 是二次剩余。
因为 $N$ 要么是二次剩余，要么是二次非剩余；要么 $N^{\frac{p-1}{2}}\equiv1(\bmod\ p)$，要么 $N^{\frac{p-1}{2}}\equiv-1(\bmod\ p)$。又因为已证 $N$ 为二次剩余和$N^{\frac{p-1}{2}}\equiv1(\bmod\ p)$ 可以互推，则 $N$ 为二次非剩余和$N^{\frac{p-1}{2}}\equiv-1(\bmod\ p)$ 也可以互推。证毕。
### Cipolla
这是一种计算 $x^2\equiv N(\bmod\ p)$ 的 $x$ 的解的方式。
对于 $N\equiv0(\bmod\ p)$ 的，有模 $p$ 意义下的唯一解 $x\equiv0(\bmod\ p)$。
对于非二次剩余 $N$，$x$ 无解，可以用欧拉准则直接除去。
剩下的就必然都是二次剩余了。
任取一个 $a$ 满足 $a^2-N$ 是二次非剩余，由于模 $p$ 意义下二次非剩余的个数接近 $\frac{p}{2}$，随机挑选 + 欧拉准则检验的期望为 $2$ 次。二次非剩余 $a^{\frac{p-1}{2}}\equiv-1(\bmod\ p)$ 这个性质在后面证明引理 1 会用到。
此处设 $i^2\equiv a^2-N$。有聪明的小朋友到这里可能就会问了，明明 $a^2-N$ 是二次非剩余，为什么还存在这么一个 $i$ 呢？这里就注意了，正如同 $x^2=-1$ 在实数范围内无解，而在虚数范围内有解 $x=\pm i$ 一样，$i^2\equiv a^2-N$ 在实数范围内也是无解的，但在虚数范围内是有解的。此处就需要我们把格局打开，把同余拓展到虚数范围内。实际上实数范围内的同余还是有大部分性质是可以带入到复数范围内的。
可以证明 $(a+i)^{p+1}\equiv N(\bmod\ p)$ 并且 $(a+i)^{\frac{p+1}{2}}$ 在模 $p$ 意义下是一个实数。
好了，为了下面的推导更加顺畅，我们先来证明两个引理。
引理1:
$i^p=i^{p-1}i=(i^2)^{\frac{p-1}{2}}i\equiv(a^2-N)^{\frac{p-1}{2}}i\equiv-i
最后这一步用到了 a^2-N 为二次非剩余，则 (a^2-N)^{\frac{p-1}{2}}\equiv-1 的结论。
引理2:
(A+B)^p\equiv A^p+B^p(\bmod\ p)
我们首先要知道二项式定理：(A+B)^p=\sum\limits_{i=0}^pC_p^iA^iB^{p-i}。
因为 C_p^i=\frac{p(p-1)(p-2)\cdots(p-i+1)}{1\times2\times3\times\cdots\times i}。当 i=0 时，C_p^i=C_p^0=1，当 i=p 时，C_p^i=C_p^p=1，当 0<i<p 时，观察分数线下面，因为 p 为素数，而分母只是小于 p 的数相乘，p 肯定不为分母的因数，而分数线上面，乘积里有 p，则 p 一定为分子的因数，则 p|C_p^i。
在模 p 意义下除了 i=0 和 i=p 的其它项都为 0，都可以消掉。则 (A+B)^p\equiv A^p+B^p(\bmod\ p)。
证明完两个引理，(a+i)^{p+1}\equiv N(\bmod\ p) 就能够很容易地推出来了。
(a+i)^{p+1}=(a+i)^p(a+i)\equiv(a^p+i^p)(a+i)\text{【引理2】}\equiv(a^p-i)(a+i)\text{【引理1】}=(a^{p-1}a-i)(a+i)\equiv(a-i)(a+i)\text{【费马小定理】}=a^2-i^2=N\text{【由}i^2=a^2-N\text{移项得】}
最后来证明一下 (a+i)^{\frac{p+1}{2}} 在模 p 意义下是实数。
因为 ((a+i)^{\frac{p+1}{2}})^2=(a+i)^{p+1}\equiv N(\bmod\ p)，此处设 (a+i)^{\frac{p+1}{2}}=A+Bi(A,B\in\Bbb{Z})，则有 (A+Bi)^2\equiv N(\bmod\ p)。
考虑使用反证法。
假设 B\not\equiv0(\bmod\ p)，把 (A+Bi)^2\equiv N(\bmod\ p) 用完全平方公式展开，得到 A^2+2ABi+B^2i^2\equiv N(\bmod\ p)，又因为最初定义的 i^2=a^2-N，所以 A^2+2ABi+B^2(a^2-N)\equiv N(\bmod\ p)。观察同余式两边，右边虚部为 0，则左边虚部也应该为 0，则 2AB\equiv0(\bmod\ p)。又因为 B\not\equiv0(\bmod\ p)，则有 A\equiv0(\bmod\ p)。故 (Bi)^2\equiv N(\bmod\ p)，进一步得 B^2i^2\equiv N(\bmod\ p)，把 B^2 移过去，得 i^2\equiv B^{-2}N(\bmod\ p)。因为 B^2 是二次剩余，由二次剩余的性质 2 得 B^{-2} 也是二次剩余，又因为 N 在最开始已经保证了其为二次剩余，由性质 1 得 B^{-2}N 也为二次剩余，而 i^2 是二次非剩余，推出矛盾。故 B 一定满足 B\equiv0(\bmod\ p)。
则 x^2\equiv N(\bmod\ p) 有整数解 (a+i)^{\frac{p+1}{2}}。
代码实现
首先用欧拉准则判一下其是否为二次剩余，不是的话，直接输出无解，否则进入下一步。
然后用随机数在每次 50\% 的概率下找到一个 a 满足 a^2-N 是模 p 意义下的二次非剩余。可以用最最一般的 rand，也可以选择质量更高的 mt19937，但放到这道题里都没什么差别。
最后开个复数类（就是下面的 complex），快速幂求一下 (a+i)^{\frac{p+1}{2}} 输出就可以了。因为此处实部只与 i^2 有关，所以记录一下 i^2，把 i 当做类似于单位虚数的东西乘一起就可以了（细微的差别是虚部相乘累加到实部上时要乘上 i^2 的值）。
代码不长，也很好写，思路倒挺妙的，实在佩服能想得到这个算法的先辈们。
代码展示
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int T;
ll N,p,i_2;
struct Complex{
ll r,i;
const Complex operator*(const Complex a){
return Complex{(r*a.r%p+i_2*i%p*a.i%p)%p,(r*a.i%p+i*a.r%p)%p};
}
};
ll qpow(ll x,ll y){
ll res=1;
while(y){
if(y&1) res=res*x%p;
y>>=1;
x=x*x%p;
}
return res;
}
bool ck(ll x){
return qpow(x,(p-1)/2)==1;
}
Complex Qpow(Complex x,ll y){
Complex res=Complex{1,0};
while(y){
if(y&1) res=res*x;
y>>=1;
x=x*x;
}
return res;
}
int main(){
mt19937 myrand(time(0));
scanf("%d",&T);
while(T--){
scanf("%lld%lld",&N,&p);
if(N==0) printf("0\n");
else if(!ck(N)) printf("Hola!\n");
else{
ll a;
do a=myrand()%(p-1)+1; while(ck((a*a-N+p)%p));
i_2=(a*a-N+p)%p;
ll x1=Qpow(Complex{a,1},(p+1)/2).r;
ll x2=p-x1;
if(x1==x2) printf("%lld\n",x1);
else{
if(x1>x2) swap(x1,x2);
printf("%lld %lld\n",x1,x2);
}
}
}
return 0;
}
有错漏不欢迎随时指出，感谢哦。