离散对数与 BSGS

对于给定的 、、 存在一个 ，使得

则称 为 在模 意义下以 为底的离散对数。

性质

离散对数有类似于一般的对数的性质

BSGS

求解离散对数问题常用的算法是 BSGS（Baby-Step Giant-Step）。

我们需要求解的方程为（ 为质数）

令 。 根据费马小定理，有 ，故若方程有解，则必然存在一个 。

设 ，其中 。

方程可化为

我们只需要找到一组 、 使得最后一个式子成立即可。

枚举 ，递推出左边 的所有取值，并将其按照 的映射关系插入到哈希表中。

之后，求出 的乘法逆元，即 。枚举 ，递推出所有的 ，每得到一个值后，从哈希表中查找该值，如果存在，取出其对应的 ， 即为一个解。

时间复杂度为 。

模板

inline void exgcd(long long a, long long b, long long &g, long long &x, long long &y)
{
    if (!b) g = a, x = 1, y = 0;
    else exgcd(b, a % b, g, y, x), y -= x * (a / b);
}

inline long long inv(long long x, long long p)
{
    long long g, r, y;
    exgcd(x, p, g, r, y);
    return (r % p + p) % p;
}

inline long long bsgs(long long a, long long b, long long p)
{
    if (a == 0) return b == 0 ? 1 : -1;

    std::map<long long, long long> map;

    long long m = ceil(sqrt(p)), t = 1;
    for (int i = 0; i < m; i++)
    {
        if (!map.count(t)) map[t] = i;
        t = t * a % p;
    }

    long long k = inv(t, p), w = b;
    for (int i = 0; i < m; i++)
    {
        if (map.count(w)) return i * m + map[w];
        w = w * k % p;
    }

    return -1;
}

EXBSGS

用 BSGS 求解离散对数需要 为质数，因为算法中用到了 的乘法逆元。实际上，只要 成立即可。

考虑方程

将它写成二元不定方程的形式

令 ，若 ，则有

即

此时 ，可以求出 的乘法逆元，乘到右边去

至此，问题转化为规模更小的子问题，继续如上过程直到 时调用 BSGS 求解即可。若过程中出现 则无解，若 则答案为 （加上之前所有减去的 ）。

模板

inline long long exbsgs(long long a, long long b, long long p)
{
    long long t, c = 0;
    while ((t = std::__gcd(a, p)) != 1)
    {
        if (b == 1) return c;
        if (b % t != 0) return -1;
        p /= t;
        b = b / t * inv(a / t, p) % p;
        c++;
    }

    long long r = bsgs(a, b, p);
    if (r == -1) return -1;
    else return r + c;
}