因为有春节,所以实际上寒假比暑假长
主要内容:原根 / 离散对数 / 二次剩余
# 目录
# 原根
下面只讨论奇素数 (p) 的原根,在不特别强调时,运算在模 (p) 意义下进行。
- 前置:阶
对于与 (p) 互质的常数 (a),在满足 (a^xequiv1) 的所有正整数 (x) 中,最小的 (x) 称为 (a) 模 (p) 的阶,记作 (ord(a))。
Theorem 1
当且仅当 $ord(a)mid x$,有 $a^xequiv 1$。
证明
假设 $a^xequiv 1$ 且 $a^yequiv 1$,则有 $a^{x+y}equiv 1$ 且 $a^{x-y}equiv 1$。
辗转相除法可得 $a^{(x,y)}equiv1$。
$(x,y)le min{x,y}$,又有 $ord(a)$ 是满足 $a^xequiv1$ 的最小 $x$,所以 $ord(d)mid x$。
Theorem 2
若 $kmid ord(a)$,则 $ord(a^k)=frac{ord(a)}k$
证明
显然有 $frac{ord(a)}k$ 是 $(a^k)^xequiv 1$ 的解(代入方程、结合 $ord(a)$ 定义即可证明),只需证明 $frac{ord(a)}k$ 是最小解。
假如存在 $x_0< frac{ord(a)}k$ 也是方程的解,则 $kx_0$ 是 $a^xequiv1$ 的解;而 $kx_0< ord(a)$,与 $ord(a)$ 定义矛盾。
根据 Theorem 1 有推论 (ord(a)mid (p-1)),证明即费马小定理。
- 原根
若在模 (p) 意义下,(x^0,x^1,cdots,x^{varphi(p)-1}) 互不相同,也即 (ord(x)=varphi(p)),则称 (x) 是 (p) 的原根,记为 (xi)。
实际上只有形如 (p^k,2p^k) 的数以及 (2,4) 有原根(虽然我不会证)。
而根据原根的定义,模 (p) 意义下的任意元素都可以表示为 (xi^k)(原根的一个重要作用)。
Theorem 3
设 $xi$ 是质数 $p$ 的一个原根,则 $xi^k$ 是原根当且仅当 $(k,p-1)=1$。
由于任意元素都可以用 (xi^k) 表示。
假设 (xi^k) 是 (p) 的原根,则必须 (ord(xi^k)=varphi(p)=p-1)。令 (h=(k,p-1))
则有 (ord(xi^k)midfrac{p-1}h)。
- 若 (h eq 1),则显然 (xi^k) 不是 (p) 的原根;
- 若 (h=1),因为 ((xi^k)^{ord(xi^k)}equiv1),则有 (xi^{kcdot ord(xi^k)}equiv1),(p-1mid ord(xi^k)),因此 (ord(xi^k)=p-1),也即 (xi^k) 是 (p) 的原根。
根据 Theorem 3,可以知道 (p) 的原根恰有 (varphi(p-1)) 个。
- 计算原根
直接从小到大枚举 awa
注意到 (p) 的原根有 (varphi(p-1)) 个,其实还是蛮多的,于是枚举不了多少个就可以找到一个最小的原根 (xi_0)。
然后再枚举 ((k,p-1)=1) 的 (k),就可以找出剩下的原根 (xi_0^k) 了。(一般不会真的让你求所有原根)
怎么验算数 (x) 是不是 (p) 的原根?
- 先验算是否 (ord(x)mid varphi(p)),直接快速幂检验 (x^{varphi(p)}) 是否为 (1) 即可;
- 再验算 (ord(x)) 是否恰好是 (varphi(p)):把 (p-1) 的所有质因子找出来记为 (P={p_1,p_2,dots,p_m}),若 (forall p_iin P,x^{frac{p-1}{p_i}} otequiv1),则 (ord(x)=varphi(p)),(x) 是原根。
- 参考实现1
int nprm,nfc,nans;
int prm[N],phi[N],vis[N],fc[N],ans[N];
bool ifrt[N]; //ifrt[i]=true: i有原根
void Init(){
//线性筛筛素数和欧拉函数
phi[1]=1;
for(int i=2;i<N;i++){
if(!vis[i]) prm[++nprm]=i,phi[i]=i-1,vis[i]=i;
for(int j=1;j<=nprm && prm[j]*i<N;j++){
vis[prm[j]*i]=prm[j];
if(i%prm[j]==0) {phi[i*prm[j]]=phi[i]*prm[j];break;}
phi[i*prm[j]]=phi[i]*(prm[j]-1);
}
}
//2,4,prime^k,2*prime^k 才有原根
ifrt[2]=ifrt[4]=true;
for(int i=2;i<=nprm;i++){
for(llong j=prm[i];j<N;j*=prm[i]) ifrt[j]=true;
for(llong j=2*prm[i];j<N;j*=prm[i]) ifrt[j]=true;
}
}
int GCD(cint a,cint b){return b? GCD(b,a%b):a;}
int QPow(int a,int b,cint MOD){
int r=1;
while(b){
if(b&1) r=1ll*r*a%MOD;
a=1ll*a*a%MOD;
b>>=1;
}
return r;
}
//把 p 的所有质因子存入 fc[1~nfc] 中
void PrimeDivide(int p){
int las=-1; nfc=0;
while(p>1){
if(las!=vis[p]) fc[++nfc]=vis[p];
las=vis[p];
p/=vis[p];
}
}
bool Check(cint x,cint p){
//先验算 x 是否满足 ord(x)|phi[p]
if(QPow(x,phi[p],p)!=1) return false;
//然后验算 ord(x) 是否是 phi[p]
for(int i=1;i<=nfc;i++)
if(QPow(x,phi[p]/fc[i],p)==1)
return false;
return true;
}
int MinRoot(cint p){ //找最小的原根
PrimeDivide(phi[p]);
for(int i=1;i<p;i++)
if(Check(i,p))
return i;
return 0;
}
void AllRoot(cint p){
nans=0;
int per=MinRoot(p),prod=1;
for(int i=1;i<=phi[p];i++){ //拓展出所有的原根
prod=(1ll*prod*per)%p;
if(GCD(i,phi[p])==1) ans[++nans]=prod;
}
}
# 离散对数
- 引入问题
求出下面方程的所有非负整数解:
其中满足 ((a,p)=1);亦可扩展至 ((a,p) eq 1)。
- BSGS(大步小步)
根据欧拉定理,当 ((a,p)=1) 时,有 (a^{varphi(p)}equiv1)。记原方程的最小正整数解为 (x_0),则原方程的解 (x) 可以表示为 (x=x_0+kvarphi(p)),于是只需要求 (x< varphi(p)) 的解。
令 (q=lfloorsqrt p floor),将原方程的解 (x) 分解为 (x=nq-m),其中 (0le m< q)。易知 (n) 的数量级与 (q) 同阶。
原方程可以写为:
由于 (n,m) 都是 (O(sqrt p)) 级别的,可以先 (O(sqrt p)) 将方程一边的所有取值都存进哈希表,然后另一边 (O(sqrt p)) 查询哈希表中是否有对应的值。
例如,将 (m=0,1,cdots,q-1) 时的全部 (ba^m) 存入哈希表,然后枚举 (n),查找哈希表中是否存在 (a^{nq})。
- exBSGS
之前提到离散对数可以扩展到 ((a,p) eq 1) 的情况,下面进行推导。
同余方程 (a^xequiv bpmod p) 有如下性质:
- 记 ((a,p)=g);
- 若 (g otmid b),则无解,可以从同余方程的本质理解:(a^x=kp+b),则 (b=a^x-kp),若有解则 (b) 必然是 (g) 的倍数;
- 若 (gmid b),则等价为 (frac{a^x}gequivfrac bgpmod{frac{p}{g}})。
于是可以转化为
方程左边相当于带了一个系数,注意到 (a) 仍有可能和 (frac pg) 不互质,只需要一直将方程同除以 ((a,p)),直到 (a,p) 互质即可。
记每一次方程整体除的数是 (g_i),(G=prod g_i),最后方程的形式大概是
求解方法还是和 BSGS 一样,用哈希表暴力储存方程一边的所有取值。
注意到我们并不能保证不存在 (x< k) 的解。在转化过程中我们直接从 (a^x) 中提取出一个 (a) 而剩下 (a^{x-1}) 其实是不严谨的,因为转化时 (a,p) 不互质,则 (a^{-1}) 不存在。
于是还要特判一下 (x<k) 有没有解。
- 参考实现2
/*
Hs 是手写的一个哈希表,作用相当于 map
*/
int GCD(int a,int b){return b? GCD(b,a%b):a;}
int exBSGS(int vara,int varb,int varp){
int total=1,add=0,mul=1,tmp=0,nowp=varp;
while((tmp=GCD(vara,nowp))!=1)
nowp/=tmp,total*=tmp,mul=1ll*(vara/tmp)*mul%varp,add++;
tmp=1;
for(int i=0;i<add;i++,tmp=1ll*tmp*vara%varp)
if(tmp==varb)
return i;
if(varb%total) return -1;
varb/=total;
//mul*vara^(x-add)=varb (mod nowp)
//mul*vara^y=varb (mod nowp)
int varq=int(ceil(sqrt(nowp))+0.5),per=1;
Hs.Clear();
tmp=varb%nowp;
for(int i=0;i<varq;i++,tmp=1ll*tmp*vara%nowp)
Hs.Insert(tmp,i),per=1ll*per*vara%nowp;
tmp=mul%nowp;
for(int i=0,res;i<=varq;i++,tmp=1ll*tmp*per%nowp)
if(~(res=Hs.Query(tmp)) && i*varq-res>=0)
return i*varq-res+add;
return -1;
}
//BSGS找最小的解
void BSGS(int varp,int varn){
varq=(int)(ceil(sqrt(varp))+0.5);
int per=1;
for(int i=0,tmp=varn;i<varq;i++,tmp=1ll*tmp*varb%varp)
Hs.Insert(tmp,i),per=1ll*per*varb%varp;
for(int i=0,tmp=1,res;i<=varq;i++,tmp=1ll*tmp*per%varp)
if(~(res=Hs.Query(tmp)) && i*varq>=res){
printf("%d
",i*varq-res);
return;
}
printf("no solution
");
}
# 二次剩余
- 引入问题
求解 (x^2equiv bpmod p),(p) 是一个奇素数。
若方程有解,则 (b) 称为 (p) 的二次剩余
- 勒让德符号
- 一些引理
Lemma 1
$$left(frac bp ight)equiv b^{frac{p-1}2}$$
简单证明一下:
- 当 (bequiv0) 时显然;
- 当 (b) 是 (p) 的二次剩余时,(exists xin[0,p),x^2equiv b);
由费马小定理有 (x^{p-1}equiv1),又有 (p) 是奇素数;
可以写成 ((x^2)^{frac{p-1}2}equiv1),则 (b^{frac{p-1}2}equiv1); - 当 (b) 不是 (p) 的二次剩余时,由逆元的唯一性可得 (1,2,cdots,p-1) 可以按照“(i) 和 (b imes i^{-1})((i) 的逆元)”的方式刚好划分为 (frac{p-1}2) 组,每组乘积为 (b);
于是把 (1,2,cdots,p-1) 全部乘起来就可以得到 ((p-1)!=b^{frac{p-1}2}),又有 ((p-1)!equiv -1)(威尔逊定理,不会 QwQ),则 (b^{frac{p-1}2}equiv-1)。
Lemma 2
$p$ 恰好有 $frac{p-1}2$ 个二次剩余。
证明如下:设 (x,y) 满足 (x^2equiv y^2)((x< y),(x,yin[1,p-1])),移项可得:
又有 (p) 是素数且 (p otmid x-y),则 ((p,x-y)=1),进而可得 (pmid x+y)。在 ([1,p-1]) 中,这样的 ((x,y)) 与 (x^2equiv y^2) 一一对应。
所以 ([1,p-1]) 中恰有 (frac{p-1}2) 个不同的 (x^2),即 (frac{p-1}2) 个二次剩余,剩下的 (frac{p-1}2) 个数则是非二次剩余。
于是有结论:(p) 的二次剩余和非二次剩余一样多。
Lemma 3
$$(a+b)^pequiv a^p+b^ppmod p$$
直接二项式展开,(a^ib^{p-i}) 项的系数为 (C_p^i)。
因为 (p) 是质数,所以当 (i eq 0,i eq p) 时,(C_p^i=frac{p!}{i!(p-i)!}) 的分子是 (p) 的倍数而分母不是,所以 (pmid C_p^i)。
取模后只剩下首尾两项。
补充一个讲课的dalao不会证所以我也不会证的定理:
Theorem 4(二次互反律)
$p,q$ 均为奇素数,则
$$left(frac pq ight)cdotleft(frac qp ight)=(-1)^{frac{p-1}2 imes frac{q-1}2}$$
- Cipolla
如果我们知道 (b) 是 (p) 的二次剩余,如何求解?
可以先随机出一个 (a) 使得 (a^2-b) 不是 (n) 的二次剩余,用勒让德函数检验即可。由于 (p) 的二次剩余和非二次剩余是一样多的,所以可以较快地随机出这个 (a)。
可以知道不存在整数 (x) 使得 (x^2=a^2-b),于是我们“扩展数域”,让这样的 (x) 存在——定义单位 (omega^2equiv a^2-b),类似于复数域,域中的所有数可以表示为 (p+qomega) 的形式。
Theorem 5
$(a+omega)^{frac{p+1}2}$ 是原方程的一个根。
直接代入证明:
(p) 是奇素数,(omega^2equiv a^2-b),则
因为 (a^2-b) 是非二次剩余,所以 ((a^2-b)^{frac{p-1}2}equiv-1)。又由费马小定理,(a^pequiv a),所以
所以
于是 (x_1=(a+omega)^{frac{p-1}2})。由 Lemma 2,另一个根 (x_2) 满足 (pmid x_1+x_2),则 (x_2equiv p-x_1)。
因为 (p) 是奇素数,(x_1,x_2) 一定奇偶性不同,则有两个不等根。
- 参考实现3
> Link 洛谷 P5491
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long llong;
#define cint const int &
int varp,conw;
int Mul(cint a,cint b){return int(1ll*a*b%varp);}
int Add(cint a,cint b){return a+b>=varp? a+b-varp:a+b;}
int Sub(cint a,cint b){return a-b<0? a-b+varp:a-b;}
int Pow(cint a,cint b){return b? Mul(Pow(Mul(a,a),b>>1),(b&1)? a:1):1;}
struct COMPLEX{
int conr,coni;
COMPLEX(){}
COMPLEX(cint varr,cint vari):conr(varr),coni(vari){}
inline friend COMPLEX operator *(const COMPLEX &A,const COMPLEX &B){
return COMPLEX(
Add(Mul(A.conr,B.conr),Mul(Mul(A.coni,B.coni),conw)),
Add(Mul(A.conr,B.coni),Mul(A.coni,B.conr))
);
}
inline COMPLEX operator ^(int varb)const{
COMPLEX vara=(*this),res(1,0);
while(varb){
if(varb&1) res=res*vara;
vara=vara*vara;
varb>>=1;
}
return res;
}
};
//p is an odd prime
int Solve(int varn){
varn%=varp;
if(Pow(varn,(varp-1)/2)==varp-1) return -1;
int vara,varw;
while(true){
vara=Mul(rand(),rand());
varw=(Sub(Mul(vara,vara),varn));
if(Pow(varw,(varp-1)/2)==varp-1) break;
}
conw=varw;
return (COMPLEX(vara,1)^((varp+1)/2)).conr;
}
int main(){
int cas;scanf("%d",&cas);
while(cas--){
int varn;scanf("%d%d",&varn,&varp);
if(!varn){printf("0
");continue;}
int ans1=Solve(varn),ans2;
if(~ans1){
ans2=varp-ans1;
if(ans1>ans2) swap(ans1,ans2);
printf("%d %d
",ans1,ans2);
}
else printf("Hola!
");
}
return 0;
}
THE END
Thanks for reading!
> Linked 余命3日少女-网易云