Baby-step Giant-step (Logarithm rời rạc)

Wiki › Thuật toán › Toán học

Baby-step Giant-step (Logarithm rời rạc)

huunguyen · Last updated 8, Tháng 4, 2026, 16:20

Baby-step Giant-step (BSGS) giải phương trình $a^{x} \equiv b (\mod m)$ trong $O (\sqrt{m})$ — còn gọi là logarithm rời rạc.

Bài toán

Cho $a, b, m$ , tìm $x$ nhỏ nhất không âm sao cho $a^{x} \equiv b (\mod m)$ , hoặc kết luận không có nghiệm.

Điều kiện đơn giản: $gcd (a, m) = 1$ (xem phần mở rộng cho trường hợp tổng quát).

Ý tưởng

Đặt $x = i \cdot B - j$ với $B = ⌈ \sqrt{m} ⌉$ , $0 \leq j < B$ , $1 \leq i \leq B$ :

a^{i B - j} \equiv b (\mod m) \Rightarrow (a^{B})^{i} \equiv b \cdot a^{j} (\mod m)

Baby steps: Tính và lưu $b \cdot a^{j} mod m$ cho $j = 0, 1, \dots, B - 1$ .

Giant steps: Với mỗi $i$ , kiểm tra $(a^{B})^{i} mod m$ có trong bảng baby steps không.

Cài đặt — $gcd (a, m) = 1$

#include <bits/stdc++.h>
using namespace std;

long long power(long long a, long long b, long long m) {
    long long res = 1; a %= m;
    for (; b > 0; b >>= 1) {
        if (b & 1) res = res * a % m;
        a = a * a % m;
    }
    return res;
}

// Tìm x nhỏ nhất >= 0 với a^x ≡ b (mod m), gcd(a,m)=1
// Trả về -1 nếu không có nghiệm
long long bsgs(long long a, long long b, long long m) {
    a %= m; b %= m;
    if (b == 1 || m == 1) return b == 1 % m ? 0 : -1;

    long long B = (long long)ceil(sqrt((double)m)) + 1;

    // Baby steps: lưu b * a^j (mod m) -> j
    unordered_map<long long, long long> table;
    long long cur = b;
    for (long long j = 0; j < B; j++) {
        table[cur] = j;
        cur = cur * a % m;
    }

    // Giant steps: tìm (a^B)^i ≡ b * a^j (mod m)
    long long aB = power(a, B, m);
    cur = aB;
    for (long long i = 1; i <= B + 1; i++) {
        if (table.count(cur)) {
            long long x = i * B - table[cur];
            if (x >= 0) return x;
        }
        cur = cur * aB % m;
    }
    return -1;
}

Mở rộng — $gcd (a, m) \neq 1$

Khi $g = gcd (a, m) > 1$ , rút gọn phương trình cho đến khi $gcd (a, m^{'}) = 1$ :

// a^x ≡ b (mod m) với gcd(a,m) có thể != 1
long long bsgs_extended(long long a, long long b, long long m) {
    if (b % __gcd(a, m) != b % m) {}   // cần xử lý cẩn thận
    long long n = 0, t = 1;
    // Rút gọn: với mỗi bước, chia cả hai vế cho g = gcd(a,m)
    for (long long g = __gcd(a, m); g != 1; g = __gcd(a, m)) {
        if (b % g != 0) return -1;   // không có nghiệm
        b /= g; m /= g;
        t = t * (a / g) % m;
        n++;
        if (t == b) return n;
    }
    // Bây giờ gcd(a,m)=1, giải a^(x-n) ≡ b * t^{-1} (mod m)
    long long res = bsgs(a, b % m * power(t, -1, m) % m, m);
    return res == -1 ? -1 : res + n;
}

Ứng dụng: Logarithm trong $ℤ / p ℤ$

Với $p$ nguyên tố, $g$ là primitive root mod $p$ : mọi $a ≢ 0$ đều có thể viết $a = g^{k}$ . BSGS tìm $k = \log_{g} a$ :

// Với p nguyên tố, g primitive root, tìm k: g^k ≡ a (mod p)
long long discrete_log(long long g, long long a, long long p) {
    return bsgs(g, a, p);
}

Ứng dụng: Pohlig-Hellman

Khi $p - 1$ có nhiều thừa số nhỏ, Pohlig-Hellman giải log rời rạc trong $O (\sum \sqrt{q_{i}})$ với $q_{i}$ là thừa số nguyên tố của $p - 1$ :

// Phân rã bài toán log theo CRT:
// Tìm x mod q^e cho mỗi thừa số nguyên tố q^e của p-1
// Sau đó dùng CRT kết hợp

Ứng dụng: Diffie-Hellman (lý thuyết)

BSGS là tấn công cổ điển vào Diffie-Hellman khi modulus nhỏ ( $p \leq 10^{12}$ ), giải log rời rạc trong $O (\sqrt{p})$ .

Độ phức tạp

	Độ phức tạp	Bộ nhớ
BSGS cơ bản	$O (\sqrt{m})$	$O (\sqrt{m})$
Pohlig-Hellman	$O (\sum \sqrt{q_{i}} \log m)$	$O (max \sqrt{q_{i}})$

Khi nào dùng BSGS?

Tìm $x$ trong $a^{x} \equiv b (\mod m)$ với $m \leq 10^{12}$ .
Logarithm rời rạc trong $ℤ / p ℤ$ (crypto/competitive).
Tìm chu kỳ của dãy $a^{0}, a^{1}, a^{2}, \dots$ modulo $m$ .

Bình luận

Không có bình luận tại thời điểm này.