BSGS 离散对数

前言

通常,高中及以下的数学研究的都是连续数学为主的.

想到对数函数,大多会想到如下的函数图像 :

BSGS 离散对数

(图片由 desmos 绘制)

但是模意义下的对数就有所不同.

模型

试求解以下方程 :

\[\large a^x \equiv b \pmod p \]

即模意义下的求对数.

BSGS 算法

全称 Baby Step Giant Step 算法.

boy step girl step

boy step gay step

拔山盖世

属实是非常暴力的做法了.

Pohlig-Hellman? 不认识,真不熟. 我连 Pollard-Rho 还没学会呢.

模板 : \(\mathtt{Link.}\)

在 \(\mathcal{O} (\sqrt{p})\) 的时间内求出形如 \(a^x \equiv b \pmod p\) 的方程,且必须满足 \(a \perp p\) .

可以发现,方程的解 \(x\) 满足 \(x \in [0,p)\)

直接枚举显然是很劣的做法,考虑如何让枚举变得均摊.

首先把 \(x\) 表示为 \(A\lceil \sqrt{p} \rceil - B\) , 可以发现只需要 \(A,B \in [0,\sqrt{p}]\) 这个范围就可以满足表示出 \([0,p)\) 内的数了.

于是我们先写出来 :

\[\large x = A\lceil \sqrt{p} \rceil - B \]

把这个表示方法代入原式 :

\[\large a^{A\lceil \sqrt{p} \rceil - B} \equiv b \pmod p \]

把负指数转到另一侧 :

\[\large a^{A\lceil \sqrt{p} \rceil} \equiv a^B b \pmod p \]

已知 \(a,b\) 那么现在可以枚举同余式右侧的 \(a^B b\) 的所有取值.

如果要求最小的 \(x\),对于两个 \(B\) 求出的 \(a^B b\) 在模 \(p\) 意义下相等的情况下,只需要保留更大的那个 \(B\) 即可.

通过上面的枚举,建立从 \(a^B b\) 到 \(B\) 的映射.

然后再枚举另一侧的 \(A\) ,求出 \(a^{A\lceil \sqrt{p} \rceil}\) 再通过映射查看是否有一个可行的 \(a^B b\) 存在.

这样就可以得出每一组能作为合法解的 \(A,B\) , 然后 \(x = A\lceil \sqrt{p} \rceil - B\) , 就是方程的解了.

可以发现, 通过把原来的暴力枚举 \(x\) 改为了成倍增加的 \(A\lceil \sqrt{p} \rceil - B\) ,大大加快了速度.

如果用 std::map 就会多一个 \(\log\) ,于是还是用哈希表比较好.

这道题里 : 手写哈希表 快于 __gnu_pbds::gp_hash_table 快于 __gnu_pbds::cc_hash_table 快于 std::unordered_map 快于 std::map , 这可太行了.

\(\texttt{Code}\) :

(附赠一个不是很可爱的哈希表)

常数太大即使是手写哈希表也只能进最优解第四页了,第一页的都是些什么神仙啊 Orz

int p,a,b;

inline int qpow(int _a,int _b) {
    int res = 1;
    while(_b) {
        if(_b & 1) res = (ll)res * _a % p;
        _a = (ll)_a * _a % p;
        _b >>= 1;
    }
    return res;
}

constexpr int SIZ = 360007;

struct Hash_table {
    Hash_table() : cnt(0) {};
    int cnt;
    int hd[SIZ];
    struct Node {
        int key;
        int val,nxt;
    }p[1000005];
    inline int hash_head(int x) {
        return x % SIZ;
    }
    inline int& operator [] (int k) {
        int h = hash_head(k);
        for(int i = hd[h]; i ;i = p[i].nxt)
            if(p[i].key == k) return p[i].val;
        p[++cnt] = (Node) {k,0,hd[h]},hd[h] = cnt;
        return p[cnt].val;
    }
}mp;

int BSGS() {
    const int mx = ceil(sqrtf(p));
    int base = b % p;
    ff(i,1,mx) {
        base = (ll)base * a % p;
        mp[base] = i;
    }
    base = qpow(a,mx);
    int prod = 1;
    ff(i,1,mx) {
        prod = (ll)prod * base % p;
        if(mp[prod])
            return (((ll)i * mx - mp[prod]) % p + p) % p;
    }
    return -1;
}

exBSGS 算法

超级拔山盖世算法

西楚霸王算法

模板 : \(\texttt{Link.}\)

考虑对于 \(a,p\) 不一定互质的情况下,求解 \(a^x \equiv b \pmod p\) .

大力把 \(\gcd\) 除掉即可.

我被卡哈希模数了阿巴阿巴阿巴阿巴.

\(\texttt{Code}\) :

int gcd(int a,int b) {
    return b ? gcd(b,a % b) : a;
}

constexpr int SIZ = 100007;

struct Hash_table {
    Hash_table() : cnt(0) {};
    int cnt;
    int hd[SIZ];
    struct Node {
        int key;
        int val,nxt;
    }p[1000005];
    inline int hash_head(int x) {
        return x % SIZ;
    }
    inline int& operator [] (int k) {
        int h = hash_head(k);
        for(int i = hd[h]; i ;i = p[i].nxt)
            if(p[i].key == k) return p[i].val;
        p[++cnt] = (Node) {k,0,hd[h]},hd[h] = cnt;
        return p[cnt].val;
    }
    inline void clear() {
        cnt = 0,mems(hd,0);
    }
}mp;

int BSGS(int a,int b,int p,int pd) {
    mp.clear();
    int mx = ceil(sqrtf(p));
    int base = 1;
    ff(i,1,mx) {
        base = (ll)base * a % p;
        mp[(ll)base * b % p] = i;
    }
    int prod = pd;
    ff(i,1,mx) {
        prod = (ll)prod * base % p;
        if(mp[prod]) {
            int res = (((ll)i * mx - mp[prod]) % p + p) % p;
            if(res >= 0) return res;
        }
    }
    return -1;
}

int exBSGS(int a,int b,int p) {
    a %= p,b %= p;
    if(b == 1 || p == 1) return 0;
    int k = 0;
    int d,pd = 1;
    while((d = gcd(a,p)) ^ 1) {
        if(b % d) return -1;
        ++k;b /= d,p /= d;
        pd = (ll)pd * a / d % p;
        if(pd == b) return k;
    }
    int res = BSGS(a,b,p,pd);
    if(res == -1) return -1;
    else return res + k;
}

例题

T1

P2485 [SDOI2011]计算器

实现如下三个功能 :

  1. 求模意义乘法幂

  2. 求线性同余方程

  3. 求高次同余方程

同余全家桶了属于是.

于是分别写快速幂,exGCD和BSGS即可.

小 心 无 解 特 判

T2

P4454 [CQOI2018]破解D-H协议

题面过长诉讼.

读完发现就是BSGS模板啊.

芜湖,一发最优解!

T3

P4861 按钮

我 : 你是BSGS吗?

P4861 : 我是欧拉函数.

我 : 你是 BSGS.

特判一个 \(N,K\) 不互质为无解即可.

然后记得求解求出的 \(x\) 需要大于 \(0\) 才行.

T4

P4884 多少个1?

首先发现并不是熟悉的高次同余方程的形式了.

然后 \(K\) 和 \(m\) 还特大.但是时间有 2s 啊

??? 我不能接受.

首先要把原式右侧变成指数形式.

同余可以左右同加 & 同乘,考虑利用这个性质.

于是左右都乘 \(9\) 然后加 \(1\) 后,左侧就转变为了 \(10^{N}\) 的形式了.

然后就发现需要快速乘,考虑 __int128_t 水过去.

结果因为替换得不彻底导致一直在调.

最后混到了最优解第三.

T5

P3306 [SDOI2013] 随机数生成器

可以发现线性同余的递推式长得一副等差数列的样子.

把系数挪一下然后把除变逆元就是一个 BSGS 能求解的标准形式了.

总结

点出来了不知道有没有用的科技树.

也不是特别难,主要就是把式子推成 \(a^x \equiv b \pmod p\) 的形式然后套板子.

板子也挺易懂的.

exBSGS 题好少啊.

CF1106F是大阴间BSGS题,明天把 CF1106 刷了吧.

CF1106 居然是 Div 2 QAQ

上一篇:第七章 ⼀致性和可⽤性的权衡结果 BASE理论


下一篇:SpringSecurity(安全)及环境搭建