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

Baby-step Giant-step (BSGS) là thuật toán giải phương trình logarithm rời rạc (discrete logarithm): cho $a,b,m$, tìm số nguyên $x\ge 0$ nhỏ nhất sao cho

$$a^x\equiv b\left(\mathrm{mod}m\right).$$

Cách ngây thơ là thử lần lượt $x=0,1,2,\dots$ và tính $a^{x}modm$ cho tới khi gặp $b$; chu kỳ của dãy lũy thừa có thể dài cỡ $m$ nên độ phức tạp là $O(m)$ — không khả thi khi $m\le {10}^{12}$. BSGS chia bài toán thành hai nửa và dùng bảng băm để chỉ duyệt $O(\sqrt{m})$ giá trị, đưa độ phức tạp xuống còn $O(\sqrt{m})$.

Điều kiện cơ bản (phần đầu bài này): $gcd(a,m)=1$. Trường hợp tổng quát được xử lý ở mục Biến thể.

Ý tưởng / Trực giác

Mọi nghiệm $x$ trong khoảng $[0,m)$ đều có thể viết dưới dạng

$$x=i·B-j,B=\lceil \sqrt{m}\rceil ,0\le j<B,1\le i\le B.$$

Vì sao tách được như vậy? Đặt $B=\lceil \sqrt{m}\rceil$ thì $B^2\ge m$, nên khi $i$ chạy từ $1$ đến $B$ và $j$ chạy từ $0$ đến $B-1$, biểu thức $i·B-j$ phủ hết mọi giá trị trong $[1,B^2]\supseteq [1,m]$. Mà chu kỳ của $a^{x}modm$ luôn $\le m$ (định lý Euler: $a^{\phi (m)}\equiv 1$ khi $gcd(a,m)=1$), nên nếu có nghiệm thì chắc chắn có một nghiệm trong khoảng này.

Thay vào phương trình và chuyển vế để tách $i$ và $j$ về hai phía:

$$a^{iB-j}\equiv b\left(\mathrm{mod}m\right)⟺a^{iB}\equiv b·a^j\left(\mathrm{mod}m\right)⟺(a^B{)}^i\equiv b·a^j(\mathrm{mod}m).$$

Đây là mấu chốt: vế phải $b·a^j$ chỉ phụ thuộc $j$, vế trái $(a^B{)}^i$ chỉ phụ thuộc $i$. Bài toán "tìm cặp $(i,j)$ làm hai vế bằng nhau" giống hệt bài toán meet in the middle (gặp nhau ở giữa):

• Baby steps (bước nhỏ): liệt kê trước tất cả vế phải $b·a^{j}modm$ với $j=0,\dots ,B-1$, lưu vào bảng băm giá_trị -> j. Mỗi bước chỉ nhân thêm một lần $a$ nên gọi là "bước nhỏ".
• Giant steps (bước lớn): với mỗi $i=1,\dots ,B$, tính $(a^B{)}^{i}modm$ rồi tra bảng. Mỗi bước nhảy một lượng $a^B$ (tương đương $B$ phép nhân $a$) nên gọi là "bước lớn".

Khi tra trúng một $j$ trong bảng, ta có $(a^B{)}^i\equiv b·a^j$, suy ra ngay $x=iB-j$. Vì duyệt $i$ tăng dần nên nghiệm tìm được đầu tiên cũng là nghiệm nhỏ nhất. Tổng cộng chỉ $O(\sqrt{m})$ phép tính cho mỗi pha.

Ví dụ chạy tay

Giải $3^x\equiv 13\left(\mathrm{mod}17\right)$, tức $a=3$, $b=13$, $m=17$.

Chọn $B=\lceil \sqrt{17}\rceil =5$.

Pha Baby steps — tính $b·a^j=13·3^{j}mod17$ và lưu bảng:

 j  | 13 * 3^j (mod 17) | ghi vào bảng
----+-------------------+--------------
 0  | 13                | {13 -> 0}
 1  | 13*3 = 39 = 5     | {5  -> 1}
 2  | 5*3  = 15         | {15 -> 2}
 3  | 15*3 = 45 = 11    | {11 -> 3}
 4  | 11*3 = 33 = 16    | {16 -> 4}

Bảng băm: {13:0, 5:1, 15:2, 11:3, 16:4}.

Pha Giant steps — đầu tiên tính $a^B=3^5=243\equiv 5\left(\mathrm{mod}17\right)$. Sau đó duyệt $i=1,2,\dots$ và tính $(a^B{)}^i=5^{i}mod17$, dò trong bảng:

 i  | 5^i (mod 17) | có trong bảng?
----+--------------+----------------------------
 1  | 5            | CÓ  ->  j = 1   <== dừng!
                   x = i*B - j = 1*5 - 1 = 4

Kiểm tra: $3^4=81=4·17+13\equiv 13\left(\mathrm{mod}17\right)$. Đúng. Vậy $x=4$.

Lưu ý cách thuật toán "gặp nhau ở giữa": vế phải đã lập sẵn ở pha baby ($13·3^1\equiv 5$), còn pha giant nhảy từng bước lớn $5^i$ và trúng ngay giá trị $5$ — tổng cộng chỉ tra vài ô thay vì thử hết $x=0,1,2,3,4$ một cách tuần tự.

Cài đặt

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

// Lũy thừa nhanh: a^b mod m, O(log b)
long long power(long long a, long long b, long long m) {
    long long res = 1 % m;
    a %= m;
    for (; b > 0; b >>= 1) {
        if (b & 1) res = (__int128)res * a % m;
        a = (__int128)a * a % m;
    }
    return res;
}

// Tìm x nhỏ nhất >= 0 với a^x ≡ b (mod m), yêu cầu gcd(a, m) = 1.
// Trả về -1 nếu vô nghiệm.
long long bsgs(long long a, long long b, long long m) {
    a %= m; b %= m;
    if (m == 1) return 0;          // mọi thứ ≡ 0 (mod 1), x = 0 thoả
    if (b == 1 % m) return 0;      // a^0 = 1 ≡ b

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

    // Baby steps: lưu b * a^j (mod m) -> j, với j = 0..B-1.
    // Dùng map để khi trùng khoá vẫn giữ j NHỎ nhất (gán đè ngược thứ tự
    // không cần thiết vì giant duyệt i tăng đã đảm bảo x nhỏ nhất).
    unordered_map<long long, long long> table;
    table.reserve(B * 2);
    long long cur = b;
    for (long long j = 0; j < B; j++) {
        // chỉ ghi nếu chưa có để giữ j nhỏ nhất cho cùng một giá trị
        if (!table.count(cur)) table[cur] = j;
        cur = (__int128)cur * a % m;
    }

    // Giant steps: tìm (a^B)^i ≡ b * a^j (mod m), i = 1..B.
    long long aB = power(a, B, m);
    cur = aB;                      // bắt đầu từ i = 1
    for (long long i = 1; i <= B; i++) {
        auto it = table.find(cur);
        if (it != table.end()) {
            long long x = i * B - it->second;
            if (x >= 0) return x;  // i tăng dần => đây là x nhỏ nhất
        }
        cur = (__int128)cur * aB % m;
    }
    return -1;                      // vô nghiệm
}

Lưu ý dùng __int128 cho mọi phép nhân vì $m$ có thể tới ${10}^{12}$, nên tích hai số cỡ $m$ vượt quá tầm của long long ($\approx 9.2\times {10}^{18}$): ${10}^{12}\times {10}^{12}={10}^{24}$.

Độ phức tạp

Lý giải: ta chọn $B=\lceil \sqrt{m}\rceil$, pha baby chạy đúng $B$ vòng (mỗi vòng một phép nhân $+$ một lần ghi bảng băm $O(1)$ trung bình), pha giant cũng chạy tối đa $B$ vòng (mỗi vòng một phép nhân $+$ một lần tra bảng $O(1)$ trung bình). Vì $B\approx \sqrt{m}$ nên cả hai pha đều $O(\sqrt{m})$. Bộ nhớ do bảng băm chứa tối đa $B$ cặp khoá–giá trị, tức $O(\sqrt{m})$. Phép lũy thừa $a^B$ thêm $O(\log m)$ nhưng bị nuốt trong tổng.

⚠️ Lỗi thường gặp

• Tràn số khi nhân (overflow). Với $m$ lớn cỡ ${10}^{12}$, tích cur * a có thể đạt ${10}^{24}$, vượt long long. Triệu chứng: kết quả sai ngẫu nhiên, đúng với test nhỏ nhưng sai test lớn. Cách tránh: ép (__int128)x * y % m ở mọi phép nhân modulo, kể cả trong power.
• Quên chuẩn hoá $b$ và xử lý $b\equiv 1$. Nếu không kiểm tra trường hợp $b\equiv 1\left(\mathrm{mod}m\right)$ (nghiệm $x=0$) thì thuật toán có thể bỏ sót hoặc trả nghiệm dương lớn hơn. Luôn a %= m; b %= m; và xét $x=0$ trước. Đặc biệt khi $m=1$ thì mọi số đều $\equiv 0$, trả về $0$.
• Áp dụng khi $gcd(a,m)\ne 1$. Hàm bsgs cơ bản giả định $a$ khả nghịch mod $m$. Nếu $gcd(a,m)>1$ (ví dụ $a=2,m=4$), nó có thể trả sai hoặc bỏ sót nghiệm nhỏ. Triệu chứng: sai trên test có $a,m$ không nguyên tố cùng nhau. Cách tránh: dùng bản mở rộng bsgs_extended ở mục dưới.
• Modulo âm. Nếu đầu vào $a$ hoặc $b$ âm, a % m trong C++ cho kết quả âm, làm hỏng bảng băm. Cách tránh: chuẩn hoá a = ((a % m) + m) % m; trước khi chạy.
• Bảng băm giữ sai $j$ khi trùng khoá. Nếu hai $j$ khác nhau cho cùng giá trị $b·a^j$, ghi đè khoá khiến nghiệm $x=iB-j$ không còn nhỏ nhất. Cách tránh: chỉ ghi khi khoá chưa tồn tại (if (!table.count(cur))) để giữ $j$ nhỏ nhất, kết hợp duyệt $i$ tăng dần.
• Chọn $B$ sai biên. Lấy $B=\lfloor \sqrt{m}\rfloor$ (làm tròn xuống) có thể khiến $B^2<m$, bỏ sót nghiệm ở cuối chu kỳ. Luôn dùng $\lceil \sqrt{m}\rceil$ và cho $i$ chạy tới $B$.

Biến thể / Mở rộng

Trường hợp $gcd(a,m)\ne 1$. Rút gọn dần phương trình: đặt $g=gcd(a,m)$, nếu $g\nmid b$ thì (sau khi đã loại nghiệm nhỏ) vô nghiệm; ngược lại chia cả $b$ lẫn $m$ cho $g$ và tích luỹ thừa số $a/g$, lặp tới khi $gcd(a,m^{\prime })=1$ rồi gọi bsgs.

// a^x ≡ b (mod m), gcd(a,m) có thể != 1
long long bsgs_extended(long long a, long long b, long long m) {
    a %= m; b %= m;
    long long n = 0, t = 1;                 // t = (a/g) tích luỹ, n = số bước đã rút
    for (long long g = __gcd(a, m); g != 1; g = __gcd(a, m)) {
        if (b == t) return n;               // nghiệm nhỏ x = n
        if (b % g != 0) return -1;          // không chia hết => vô nghiệm
        b /= g; m /= g;
        t = (__int128)t * (a / g) % m;
        n++;
        if (m == 1) return n;               // mọi số ≡ 0 (mod 1)
    }
    if (t == b % m) return n;
    // Giờ gcd(a,m)=1: giải a^(x-n) ≡ b * t^{-1} (mod m), nghịch đảo bằng Fermat/Euler
    // Khi m nguyên tố: t^{-1} = t^{m-2}. Tổng quát dùng nghịch đảo Euler.
    long long inv_t = power(t, m - 2, m);   // chỉ đúng khi m nguyên tố
    long long res = bsgs(a, (__int128)b * inv_t % m, m);
    return res == -1 ? -1 : res + n;
}

Lưu ý: nghịch đảo t^{m-2} chỉ đúng khi $m$ nguyên tố. Với $m$ tổng quát sau khi rút, cần nghịch đảo bằng thuật toán Euclid mở rộng vì lúc đó luôn có $gcd(t,m)=1$.

Ứng dụng — log rời rạc trong $\mathbb{Z}/p\mathbb{Z}$. Với $p$ nguyên tố và $g$ là căn nguyên thuỷ (primitive root), mọi $a\not\equiv 0$ viết được $a=g^k$; BSGS tìm $k={\log }_{g}a$. Đây là nền tảng của nhiều bài mật mã và tổ hợp số học.

Tìm chu kỳ / bậc nhân (multiplicative order). Bậc của $a$ mod $m$ là số $x>0$ nhỏ nhất với $a^x\equiv 1$; có thể tìm bằng BSGS với $b=1$ (loại nghiệm $x=0$).

Bài tập luyện

CTOJ hiện chưa có bài thuần BSGS/logarithm rời rạc trong pool công khai; các bài dưới đây rèn luyện đúng bộ công cụ mà BSGS được xây dựng trên đó: lũy thừa modular nhanh, bậc nhân (multiplicative order) và cấu trúc chu kỳ của ánh xạ nhân modulo. Sắp dễ → khó:

• Đường đi trong đồ thị I (graphpath1) — (Advanced) Đếm số đường đi đúng $k$ cạnh với $k\le {10}^9$: luyện lũy thừa nhanh (trên ma trận) — chính là phép $a^B$ và lặp $a^x$ làm lõi của BSGS.
• Đường đi trong đồ thị II (graphpath2) — (Advanced) Biến thể min-plus của bài trên với $k\le {10}^9$: củng cố kỹ thuật nhân lặp theo lũy thừa của số mũ lớn, tư duy "chia nhỏ số mũ" giống Baby/Giant step.
• Số học mô-đun (modarith) — (Advanced) Đếm hàm $f$ thoả $kf(x)\equiv f(kxmodp)$: buộc phải phân tích cấu trúc chu kỳ và bậc nhân của $k$ mod $p$ — đúng tư duy log rời rạc và độ dài chu kỳ lũy thừa.
• Cấu Hình Kỳ Diệu (gymnasts) — (Expert) Đếm cấu hình tuần hoàn với $N\le {10}^{12}$, dựa trên $gcd$ và chu kỳ chia hết: rèn lập luận chu kỳ/ước số nguyên tố cùng nhau và lũy thừa modular trên dải ${10}^{12}$ — đúng quy mô $m$ mà BSGS nhắm tới.