二次剩余
概念
有奇素数$p$，整数$a$满足$p\not | a$，若存在整数$x$使得
$$x^2 \equiv a\pmod{p}$$
则称$a$为模$p$的二次剩余（Quartatic Residue，简称QR），否则为非二次剩余（Non-Quartatic Residue，简称NR）。
有几个重要的性质：
1、模$p$的二次剩余恰好有$\frac{p-1}{2}$个
2、$QR\times QR=QR, QR\times NR=NR, NR\times NR=QR$
勒让德（Legendre）符号
定义勒让德符号
欧拉判定准则
欧拉判定准则（Euler's criterion）：
$$\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}\pmod{p}$$
特别地，若$a$是QR，则$a^{\frac{p-1}{2}}\equiv 1\pmod{p}$；若$a$是NR，则$a^{\frac{p-1}{2}}\equiv -1\pmod{p}$。这两条都是可逆的。
证明：
利用费马小定理做扩展：
$$a^{p-1}\equiv 1\pmod{p}$$
得到：
$$a^{p-1}-1=(a^{\frac{p-1}{2}}-1)(a^{\frac{p-1}{2}}+1)$$
也就是说
$$(a^{\frac{p-1}{2}}-1)(a^{\frac{p-1}{2}}+1)\equiv 0\pmod{p}$$
所以说对于任意的$(a,p)=1$，都有$a^{\frac{p-1}{2}}\equiv \pm 1\pmod{p}$
这也证明了之前所说的性质一，即模$p$的二次剩余恰好有$\frac{p-1}{2}$个。可以想到，$1$到$p-1$中，有$\frac{p-1}{2}$个二次剩余，$\frac{p-1}{2}$个非二次剩余，正好对应$1$和$-1$两个解。
勒让德符号的常见性质
1、$\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)=\left(\frac{ab}{p}\right)$，利用欧拉判定准则显然易证。这也说明，勒让德符号是完全积性的。
2、$\left( \frac{a+kp}{p} \right)=\left( \frac{a}{p} \right)$，模运算的性质显然可得。
3、$\left( \frac{a^2}{p} \right)=1$，由勒让德符号的完全积性性质可得。
4、二次互反律：对于奇素数$p\neq q$，有：
$$\left( \frac{q}{p} \right)\left( \frac{p}{q} \right)=(-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}$$
练习1：计算$\left(\frac {3}{7} \right)$
解：
由欧拉判定准则，有：
$$\left(\frac {3}{7} \right)\equiv 3^{\frac{7-1}{2}}\pmod{7}$$
计算得：
$$3^{\frac{7-1}{2}}\equiv 3^3\equiv -1\pmod{7}$$
所以$\left(\frac {3}{7} \right)=-1$，即$3$是$7$的非二次剩余。
练习2：证明之前讲的性质二，也就是$QR\times QR=QR, QR\times NR=NR, NR\times NR=QR$。
证明：
利用勒让德符号的完全积性性质可以证明，这里不再赘述。
-1是素数p的二次剩余的情况
结论：
$-1$是奇素数$p$的二次剩余当且仅当$p\equiv 1\pmod 4$，也就是：
证明：
由欧拉判定准则，有：
$$\left(\frac{-1}{p}\right)\equiv (-1)^{\frac{p-1}{2}}\pmod{p}$$
若$p\equiv 1\pmod 4$，则对于某个整数$k$有$p=4k+1$，所以有：
$$(-1)^{\frac{p-1}{2}}=(-1)^{2k}=1$$
所以$\left(\frac{-1}{p}\right)=1$，即$-1$是$p$的二次剩余。
若$p\equiv -1\pmod 4$，则对于某个整数$k$有$p=4k+3$，所以有：
$$(-1)^{\frac{p-1}{2}}=(-1)^{2k+1}=-1$$
所以$\left(\frac{-1}{p}\right)=-1$，即$-1$不是$p$的二次剩余。
p mod 4=3 时的解
如果$p\equiv -1\pmod 4$，$p$依旧是奇素数，$\left(\frac{a}{p}\right)=1$，那么$x^2\equiv a\pmod{p}$的解为$a^{\frac{p+1}{4}}$。证明：
Cipolla算法
对于形如$x^2\equiv a\pmod{p}$的方程，如果$a$是QR，那么方程有解，否则方程无解。
算法流程：
- 找到一个数字$b$，使得$b^2-a$不是二次剩余，即$\left(\frac{b^2-a}{p}\right)=-1$。
- 引入复数，设$i^2=b^2-a$，所以$a=b^2-i^2$。
- $(b+i)^{\frac{p+1}{2}}$就是一个解，模意义下的相反数就是另外一个解。
首先，第一步中，我们可以随机去找这个数字$b$，因为二次剩余和非二次剩余的数量都是$\frac{p-1}{2}$，所以期望上两次就能找到。
可知：
$$i^p\equiv -i\pmod p$$
因为：
$$i^p\equiv i(i^2)^{\frac{p-1}{2}}\equiv i(b^2-a)^{\frac{p-1}{2}}\ \equiv i\left(\frac{b^2-a}{p} \right)\equiv -i$$
其次，上面所说的$i$怎么表示呢？
之前说的是：$i^2=b^2-a$，并且$b^2-a$不是二次剩余。也就是说$i=\sqrt{b^2-a}$，但是模意义下没有开方运算，所以我们需要用复数来表示。也就是说，$b+i$就是一个复数。
接下来，先看一个定理，对于两个整数$A,B$，满足：
$$(A+B)^p \pmod p=A^p+B^p \pmod p$$
这个我们可以使用二项式定理来进行证明。
证明：
观察组合数公式：
$$C_p^i=\frac{p!}{i!(p-i)!}$$
可以发现，只要是$i\neq 0,i\neq p$，那么$C_p^i$都是$p$的倍数，所以：
QED。
接下来看，为什么$(b+i)^{\frac{p+1}{2}}$是一个解。
也就是说：
$$((b+i)^{\frac{p+1}{2}})^2\equiv a \pmod p$$
最后，$(b+i)^{\frac{p+1}{2}}$的虚部系数一定是$0$吗？
一定是。证明：
采用反证法，假设虚部不为零，也就是说存在：
$$(A+Bi)^2\equiv a\pmod p$$
并且$B\neq 0$，那么：
可以发现方程左侧是一个整数，右侧是一个复数，这两者相等。这代表着，右侧虚部的系数一定是$0$，也就是说$AB\equiv 0\pmod p$。
之前假设$B\neq 0$，所以$A\equiv 0\pmod p$，也就是说：
$$(Bi)^2\equiv a\pmod p$$
根据之前定义，$A+Bi$是个二次剩余，$A=0$也就是说$(Bi)^2$是个二次剩余。又因为之前定义$i^2$是个非二次剩余，根据$NR\times NR=QR$的原则，所以$B^{2}$是个非二次剩余。
但是显然可见，$B$是一个非零整数，所以$B^2$一定是一个二次剩余，产生了矛盾。所以可见虚部系数$B$一定是$0$。
模板题代码:
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll I;//i^2对应的值
ll n,p;
struct Cp{
ll A,B;//表示复数A+Bi
Cp(ll _A=0,ll _B=0):A(_A),B(_B){}
Cp operator*(const Cp& t)const{
Cp ans;
ans.A=(A*t.A%p+B*t.B%p*I%p)%p;
ans.B=(A*t.B%p+B*t.A%p)%p;
return ans;
}
};
ll qpow(ll a,ll b,ll mod){
ll ans=1;
while(b){
if(b&1) ans=ans*a%mod;
a=a*a%mod;
b>>=1;
}
return ans%mod;
}
Cp qpow(Cp a,ll b){
Cp ans(1,0);
while(b){
if(b&1) ans=ans*a;
a=a*a;
b>>=1;
}
return ans;
}
int Legendre(ll a,ll p){
if(qpow(a,(p-1)>>1,p)==1) return 1;
return -1;
}
ll Cipolla(ll a,ll p){
ll b=rand()%p+1;
while(Legendre((b*b%p-a+p)%p,p)==1) b=rand()%p+1;
I=(b*b%p-a+p)%p;
return qpow(Cp(b,1),(p+1)>>1).A;
}
int main(){
int T;
scanf("%d",&T);
while(T--){
scanf("%lld%lld",&n,&p);
if(!n){
printf("0\n");
continue;
}
if(Legendre(n,p)==-1) printf("Hola!\n");
else{
ll A=Cipolla(n,p);
ll B=(p-A)%p;
if(A>B) swap(A,B);
if(A==B) printf("%lld\n",A);
else printf("%lld %lld\n",A,B);
}
}
return 0;
}
发表评论