概念

Baby Step Giant Step(BSGS) 即大步小步算法

可以在在$O(\sqrt{m})$求解模方程(离散对数问题)

$a^x \equiv b \pmod m \;\; 0 \leq x < m$

BSGS

令$n = \lfloor m \rfloor$
设$x = An + B$,其中$0 \leq A,B < n$
$a^{An+B} \equiv b \pmod m$
两边同时乘以$a^B$的逆元 (所以要保证gcd(a,m) = 1)
$a^{An} \equiv ba^{-B} \pmod m$

先计算右边部分的值,存入Hash表
然后从小到大枚举A,看在表中是否存在

有一个技巧不用求逆元
设$x = An - B$,其中$0 < A \leq n+1$,$0 \leq B < n$

p.s. 仍要保证gcd(a,m) = 1

扩展BSGS

gcd(a,m) != 1

将模方程转化为如下形式
$a^x + km = b, k \in \mathbb{Z}$
设$g = gcd(a,m)$,若$g \nmid b$,则该方程一定无解
两边同除以$g$

$\frac{a}{g} a^{x-1} + k \frac{m}{g} = \frac{b}{g}, k \in \mathbb{Z}$

模方程就转化为了

$\frac{a}{g} a^{x-1} \equiv \frac{b}{g} \pmod {\frac{m}{g}}$

令$m’ = m/g,b’ = b/g(a/g)^{-1},x’ = x + 1$

得到新的模方程

$a^{x’} \equiv b’ \pmod {m’}$

迭代若干次直到gcd(a,m) = 1
求解出$x’$,则$x = x’ + cnt$,cnt为迭代次数

模板

SPOJ-MOD

扩展BSGS求离散对数问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double DB;

#define F(i,a,b) for(int i=(a);i<=(b);++i)
#define R(i,n) for(int i=0;i<(n);++i)
#define fill(a,b) memset(a,b,sizeof(a))
#define gcd __gcd

map<LL,LL> vis;

LL pow_m(LL a,LL n,LL mod)
{
LL res = 1;
while(n)
{
if(n&1) res = res*a %mod;
a = a*a %mod;
n >>= 1;
}
return res;
}

LL bsgs(int a,int b,int m)
{
a %= m,b %= m;
if(b == 1) return 0;
int n = int(sqrt(1.0*m) + 1),cnt = 0;
LL t = 1;
for(int g = gcd(a,m);g != 1;g = gcd(a,m))
{
if(b % g) return -1;
m /= g, b /= g, t = a/g*t %m;
++cnt;
if(b == t) return cnt;
}

vis.clear();
LL base = b;
R(i,n) vis[base] = i,base = base*a %m;
base = pow_m(a,n,m);
F(i,1,n+1)
{
t = t * base %m;
if(vis.count(t))
return 1LL*n*i - vis[t] + cnt;
}
return -1;
}

int main()
{
//freopen("test.txt","r",stdin);
int a,m,b;
while(scanf("%d %d %d",&a,&m,&b),a)
{
LL ans = bsgs(a,b,m);
if(ans == -1) puts("No Solution");
else printf("%lld\n",ans);
}
return 0;
}

参考资料