BSGS 算法

求解 A^x ≡ B mod C  C是质数 的最小非负整数解

证明:A^x ≡ A^(x%φ(C)) mod C

A^(x%φ(C))  ≡ A^(x-k*φ(C)) ≡ (A^x)/ A^(k*φ(C)) ≡ A^x mod C

所以枚举的话,x只需要枚举[0,φ(c)-1]

若x在[0,φ(C)-1]范围内有解,则同余方程有解,否则无解

令m=ceil(sqrt(m)),x=i*m-j

A^(i*m-j) ≡ B mod C

A^(i*m) ≡ B* A^j  mod C

将 B* A^j modC   j∈[1,m]  存入哈希表

从小到大枚举i,找到的第一个 A^(i*m)  mod C在哈希表中,i*m-j 就是答案

为什么 m=ceil(sqrt(C))

因为 x<φ(C)=C-1,所以 i*m-j<C-1,i*m<C-1+j

i∈[1,m],所以 m<sqrt(C-1+j)

为什么找到的最小的i,i*m-j 就是答案

因为在将 B* A^j 存入哈希表时,值如果相同的话,会用大的j替换小的j

i*m-j ,i相同时,j越大值越小

从小到大枚举i,A^(i*m) 的增长幅度 要大于A^j,所以i越小越好

void bsgs()
{
mp.clear();
int m=ceil(sqrt(C));
int mul=B;
mp[B]=0;
for(int j=;j<=m;++j)
{
mul=1LL*A*mul%C;
mp[mul]=j;
}
int am=Pow(A,m,C);
mul=;
for(int j=;j<=m;++j)
{
mul=1LL*mul*am%C;
if(mp.find(mul)!=mp.end())
{
printf("%d\n",j*m-mp[mul]);
return;
}
}
puts("No solution");
}
上一篇:五子棋游戏SRS文档


下一篇:【EXPDP】expdp/impdp数据泵远程导入导出