Дискретное логарифмирование: baby-step giant-step для a^x ≡ b (mod m) — как и за сколько?

Baby-step giant-step (BSGS) решает a^x ≡ b (mod m) за O(sqrt m) времени и памяти. Идея — meet in the middle. Представим x = i·n − j, где n = ceil(sqrt(m)), 0 ≤ i ≤ n, 0 ≤ j < n. Тогда уравнение превращается в a^{i·n} ≡ b·a^{j} (mod m).

Алгоритм:

1. Baby steps: для всех j от 0 до n-1 кладём в хеш-таблицу b·a^j mod m → j.
2. Giant steps: для всех i от 1 до n считаем a^{i·n} mod m и ищем в таблице. Нашли совпадение → x = i·n − j.

long long bsgs(long long a, long long b, long long m) { // m простое, a не кратно m
    a %= m; b %= m;
    long long n = (long long)sqrt((double)m) + 1;
    unordered_map<long long, long long> table;
    long long cur = b;
    for (long long j = 0; j < n; j++) {            // baby steps: b * a^j
        table[cur] = j;
        cur = cur * a % m;
    }
    long long an = binpow(a, n, m);                // a^n
    cur = 1;
    for (long long i = 1; i <= n; i++) {           // giant steps: a^(i*n)
        cur = cur * an % m;
        if (table.count(cur))
            return i * n - table[cur];
    }
    return -1; // решения нет
}

Время и память — O(sqrt m). Кладём b·a^j сначала и берём наименьший подходящий x (поэтому при коллизии в таблице оставляем больший j или перебираем i по возрастанию).