BSGS学习笔记

对于一个式子

\(\quad\quad at\equiv b (mod\ p)\)

我们可以用扩展欧几里得算法求解

而对于这个式子

\(\quad\quad a^t\equiv b (mod\ p), (a,p)=1\)

我们就要用\(BSGS\)求解了

根据欧拉定理

\(\quad\quad (a,p)=1\rightarrow a^{\phi(p)}\equiv 1(mod\ p)\)

由此我们可以把\([0,\phi(p)-1]\)分块，但是因为\(\phi(p)\)难求，为了代码简单，我们可以在\([0,p]\)间分块，分成\(\sqrt{p}块\)， 长度\(k=[\sqrt{p}]+1\)

设\(t=kx-y, x\in [1,k], y\in [0, k-1]\)
则\(t\in [1,k^2]\)，然后特判\(t=0\)，即可枚举所有。

为什么用减法？ 可以移项。

为什么\(x\)不从\(0\)开始？ \(BSGS\)一般求的是最小的\(t\), 如果x取零，\(t\)有可能小于零，增加式子的不确定性。

如何快速判断是否符合条件？ 每次对于每个固定的\(x\)，判断是否存在一个\(y\)符合条件 —— 哈希表.

code

int bsgs(int a, int b, int p)
{
    if (1 % p == b % p) return 0;
    int k = sqrt(p) + 1;
    unordered_map<int, int> hash;
    for (int i = 0, j = b % p; i < k; i ++ )
    {
        hash[j] = i;
        j = (LL)j * a % p;
    }
    int ak = 1;
    for (int i = 0; i < k; i ++ ) ak = (LL)ak * a % p;

    for (int i = 1, j = ak; i <= k; i ++ )
    {
        if (hash.count(j)) return (LL)i * k - hash[j];
        j = (LL)j * ak % p;
    }
    return -1;
}