离散对数与 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;
}