大步小步算法（BSGS）详解

BSGS（Baby Step Gaint Step）算法详解

BSGS算法是用于求解形如$A^x\equiv B(\mathrm{m}\mathrm{o}\mathrm{d}P)$的高次同余方程，其中$A,B,P$为已知，且要求$\gcd (A,P)=1$是一个质数。

前置知识

• 哈希

算法分析

先证明一个结论：若原方程有解，则$x\in [0,P?1)$一定有解。

因为$\gcd (A,P)=1$，由费马小定理得$A^{P?1}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}P)$。

则有$A^{x+k(P?1)}\equiv A^x(\mathrm{m}\mathrm{o}\mathrm{d}P)$，其中$k$为整数。

换句话说就是出现了循环。这样一来，这个方程的最小解就一定在$[0,P?1)$中了。

我们设$x=am?b$，其中$m$为任意一个正数，且有$a\in [0,m)$。

那么变一下形就发现$A^{am}\equiv B?A^b(\mathrm{m}\mathrm{o}\mathrm{d}P)$。

我们暴力算出右边的$B?A^b\mathrm{m}\mathrm{o}\mathrm{d}P$的所有可能的值，并存起来。

然后再枚举左边的$a$，并查询在右边有没有相等的值。

所以这个算法的复杂度为$O(\max (m,\frac{P}{m}))$。可以证明当$m=\sqrt{P}$时，算法的复杂度达到下界，为$O(\sqrt{P})$。

就这么简单QAQ…

当然为了查询方便，我们写一个哈希或者直接用map存下右边所有的值即可。

这里建议用哈希，因为用map的话会多出一个$\log$。

模版

struct HashTable {
    struct HashNode {
    int u, v;HashNode *nxt;};HashNode pool[HashMod * 20 + 5];HashNode *hcnt, *head[HashMod + 5];void clear() {
    hcnt = &pool[0], memset(head, 0, sizeof head);}void addnode(int u, int v, int w) {
    HashNode *p = ++hcnt;p->u = w, p->v = v;p->nxt = head[u], head[u] = p;}void hash(int x, int k) {
    int s = x % HashMod;addnode(s, k, x);}int query(int x) {
    int s = x % HashMod;for(HashNode *p = head[s]; p != NULL; p = p->nxt)if(p->u == x) return p->v;return -1;}
};
HashTable hashtab;
ll BabyStepGaintStep(ll y, ll z, ll p) {
    if(y % p == 0) return -1;y %= p, z %= p;if(z == 1) return 0;hashtab.clear();ll m = (ll) sqrt(p) + 0.5;for(ll i = 0, t = z; i < m; i++, t = t * y % p)hashtab.hash(t, i);for(ll i = 1, tmp = QuickPow(y, m, p), t = tmp; i <= m + 1; i++, t = t * tmp % p) {
    ll k = hashtab.query(t);if(k == -1) continue;return i * m - k;}return -1;
}