【学习笔记】BSGS & ExtendedBSGS

发表于

BSGS（Baby-Step-Giant-Step）算法，用来解决 $A^x \equiv B \pmod{C}(0 \leq x < C)$ 这样的问题。

具体讲BSGS算法之前，先介绍一下离散对数。

在整数中，离散对数（英语：Discrete logarithm）是一种基于同余运算和原根的一种对数运算。简单来说，离散对数就是在同余意义下的对数运算。

原始的 $\text{BSGS}$ 要求 $C$ 是素数，拓展 $\text{BSGS}$ 则可以处理 $C$ 不是素数的情形。

$\text{BSGS}$

我们令 $m = \left \lceil \sqrt{C} \right \rceil $ ，那么 $x$ 可以表示为 $i m+j$ 这样的形式，则 $A^x = A^{m^i} A^j$ ，其中 $0\leq i<m$ , $0 \leq j < m$ 。

我们接下来就可以在 $\Theta(\sqrt{C})$ 的时间内枚举 $i$ ，我们令 $D = A^{m^i}$ ，则 $D*A^j \equiv B \pmod{C}$ ，就可以用 $\text{ExtendedGCD}$ 求解出 $A^j$ ，因为 $C$ 是素数，除了 $A$ 是 $C$ 的情况要特判以外总有 $GCD(D, C) = 1$ ，即这个方程总是有解的。

现在我们求出了 $A^j$ ，怎么快速知道 $j$ 的值呢，由于是模 $C$ 意义，所以直接套上对数肯定不合适，那我们可以查表啊！先用 $\Theta(\sqrt{C})$ 的时间内将 $A^k, 0\leq k<m$ 的值全部插进哈希表（想省事的可以考虑一下 $\text{map}$ ，就是复杂度大了点）里面，最后直接 $\Theta(1)$ 查表就可以了。

$\text{ExtendedBSGS}$

$\text{ExtendedBSGS}$ 不要求 $C$ 是素数，主要思想就是约简 $C$ ，使它变成一个素数。

首先，要了解同余有以下性质：

$(k, m) = d$ , $ka \equiv kb \pmod{m}$ $\Rightarrow$ $a \equiv b \pmod{\frac{m}{d}}$

特殊的，$ka \equiv kb \pmod{m} \Rightarrow$ $a \equiv b \pmod{m}$

那么我们就可以来讲如何消去因子了。

我们可以每次消去 $GCD(A, C)$ ，如果 $GCD(A, C)$ 不能整除 $B$ ，那肯定是没有解的.

接下来考虑 $GCD(A, C) \ |\ B$ 的情况。

这样子就给出了单步的计算过程，具体操作就是在 $B$ 和 $C$ 中除掉 $GCD(A, C)$ ， 用一个临时变量 $D$ 每次乘 $A / GCD(A, C)$ ，同时用累加器 $cnt$ 每次累加 $1$ ，$A$ 不变。

最后，问题就转化为 $D * A^{x - cnt} \equiv B \pmod{C}$ ，接下来就又是 $BSGS$ 的活儿了。

但是有一点需要注意，在后面的时候我们默认了 $x$ 是大于等于$cnt$ 的，但是很明显 $x < cnt$ 的解也是可能存在的。那么我们只需要在之前做 $\Theta(\log_2C)$ 次枚举排除这种情况就可以了。

$\text{Code}$

哈希就略过了~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
//------------------- BSGS ---------------------
int ExtendedGCD(int a, int b, int& x, int& y) {
	if (a == 0 && b == 0) return -1;
    if (b == 0) {
        x = 1; y = 0;
        return a;
    }
    int value = ExtendedGCD(b, a % b, y, x);
    y -= a / b * x;
    return value;
}
int BSGS(int A, int B, int C) {
	A %= C;
    if (!A) return B ? -1 : 1;
    int root = static_cast< int >(std::ceil(std::sqrt(C)));
    hash.clear();
    int base = 1;
    for (int i = 0; i < root; i++) {
        hash.insert(base, i);
        base = base * A % C;
    }
    int j = -1, D = 1;
    for (int i = 0; i < root; i++) {
        int x, y, z = ExtendedGCD(D, C, x, y);
        int c = C / z;
        x = (x * B / z % c + c) % c;
        j = hash.query(x);
        if (j != -1) return i * root + j;
        D = D * base % C;
    }
    return -1;
}

//----------------- Extended BSGS -----------------

int ExtendedGCD(int a, int b, int& x, int& y) {
	if (a == 0 && b == 0) return -1;
    if (b == 0) {
        x = 1; y = 0;
        return a;
    }
    int value = ExtendedGCD(b, a % b, y, x);
    y -= a / b * x;
    return value;
}
int ExtendedBSGS(int A, int B, int C) {
    int tmp = 1, cnt = 0, D = 1;
    for (int i = 0; i < 40; i++) {
        if (tmp == B) return i;
        tmp = tmp * A % C;
    }
    for (int x, y, gcd = ExtendedGCD(A, C, x, y); gcd != 1; gcd = ExtendedGCD(A, C, x, y), cnt++) {
        if (B % gcd) return -1;
        B /= gcd; C /= gcd;
        D = D * A / gcd % C;
    }
    int root = static_cast< int >(std::ceil(std::sqrt(C)));
    hash.clear();
    int base = 1;
    for (int i = 0; i < root; i++) {
        hash.insert(base, i);
		Map[base] = i;
        base = base * A % C;
    }
    int j = -1;
    for (int i = 0; i < root; i++) {
        int x, y, z = ExtendedGCD(D, C, x, y), c = C / z;
        x = (ModularMul(x, B, c) / z % c + c) % c;
        j = hash.query(x);
        if (j != -1) return i * root + j + cnt;
        D = D * base % C;
    }
    return -1;
}