Мотивация и контекст

Представьте задачу: дано простое число $p = 10^9 + 7$, числа $a$ и $b$. Найти $x$ такое, что $a^x \equiv b \pmod{p}$. Это классическая задача дискретного логарифма — она встречается в олимпиадных задачах, криптографии (протоколы Диффи-Хеллмана, ElGamal, DSA), и теории чисел. В отличие от обычного логарифма, вычислить дискретный логарифм вычислительно сложно, и именно на этой сложности основана безопасность большинства криптографических систем.

Но прежде чем перейти к алгоритмам поиска дискретного логарифма, необходимо понять структуру мультипликативной группы $\mathbb{Z}_p^*$. Ключевым инструментом здесь служат примитивные корни — генераторы этой группы. Понимание примитивных корней открывает путь к изоморфизму $\mathbb{Z}_p^* \cong \mathbb{Z}_{p-1}$, что радикально упрощает работу с степенями и логарифмами по модулю.

В соревновательном программировании дискретный логарифм применяется в задачах на:

• Нахождение $n$-го члена линейной рекуррентности с помощью теоремы Эйлера-Ферма
• Подсчёт количества решений уравнений вида $x^k \equiv c \pmod{p}$
• Задачи о порядках элементов и структуре групп
• Криптографические конструкции в задачах CTF-стиля

Теория

Порядок элемента в группе $\mathbb{Z}_p^*$

Пусть $p$ — простое число. Рассмотрим мультипликативную группу $\mathbb{Z}_p^* = \{1, 2, \ldots, p-1\}$ с операцией умножения по модулю $p$.

Определение. Порядком элемента $a \in \mathbb{Z}_p^*$ называется наименьшее натуральное число $\text{ord}(a)$ такое, что $a^{\text{ord}(a)} \equiv 1 \pmod{p}$.

Теорема 10.1 (основные свойства порядка).

1. $a^k \equiv 1 \pmod{p}$ тогда и только тогда, когда $\text{ord}(a) \mid k$.
2. $\text{ord}(a) \mid p - 1$ (следствие малой теоремы Ферма).
3. $\text{ord}(a^k) = \text{ord}(a) / \gcd(\text{ord}(a), k)$.

Доказательство (п.1). Пусть $k = q \cdot \text{ord}(a) + r$, где $0 \le r < \text{ord}(a)$. Тогда $a^k = (a^{\text{ord}(a)})^q \cdot a^r \equiv a^r \pmod{p}$. Значит, $a^k \equiv 1$ тогда и только тогда, когда $a^r \equiv 1$. По минимальности порядка это возможно лишь при $r = 0$, то есть $\text{ord}(a) \mid k$. $\square$

Доказательство (п.2). Из малой теоремы Ферма: $a^{p-1} \equiv 1 \pmod{p}$. По п.1 получаем $\text{ord}(a) \mid p - 1$. $\square$

Доказательство (п.3). Обозначим $d = \gcd(\text{ord}(a), k)$ и $T = \text{ord}(a)$. Нужно найти наименьшее $m$ такое, что $(a^k)^m \equiv 1$, то есть $a^{km} \equiv 1$, то есть $T \mid km$. Это равносильно $\frac{T}{d} \mid \frac{k}{d} \cdot m$. Поскольку $\gcd(\frac{T}{d}, \frac{k}{d}) = 1$, получаем $\frac{T}{d} \mid m$. Наименьшее такое $m$ равно $\frac{T}{d} = \frac{T}{\gcd(T, k)}$. $\square$

Примитивный корень

Определение. Элемент $g \in \mathbb{Z}_p^*$ называется примитивным корнем (или генератором) по модулю $p$, если $\text{ord}(g) = p - 1$, то есть $g$ порождает всю группу $\mathbb{Z}_p^*$.

Теорема 10.2 (существование примитивного корня). Для любого простого числа $p$ существует примитивный корень по модулю $p$.

Доказательство. $\mathbb{Z}_p^*$ — циклическая группа порядка $p-1$. Докажем это.

Пусть $p - 1 = q_1^{e_1} q_2^{e_2} \cdots q_k^{e_k}$ — факторизация. Для каждого $i$ уравнение $x^{(p-1)/q_i} \equiv 1 \pmod{p}$ имеет не более $(p-1)/q_i$ решений (многочлен степени $(p-1)/q_i$ над полем $\mathbb{F}_p$). Значит, существует элемент $a_i$, для которого $a_i^{(p-1)/q_i} \not\equiv 1 \pmod{p}$.

Из свойств порядка: $\text{ord}(a_i) \mid p-1$, но $\text{ord}(a_i) \nmid (p-1)/q_i$. Следовательно, $q_i^{e_i} \mid \text{ord}(a_i)$.

Рассмотрим $g = \prod_i a_i^{(p-1)/q_i^{e_i}}$. Можно показать (используя теорему о порядке произведения независимых элементов), что $\text{ord}(g) = \prod_i q_i^{e_i} = p - 1$. Таким образом, $g$ — примитивный корень. $\square$

Следствие. Примитивных корней по модулю $p$ ровно $\phi(p-1)$.

Доказательство. Если $g$ — примитивный корень, то все элементы $\mathbb{Z}_p^*$ имеют вид $g^k$, $0 \le k < p-1$. По теореме 10.1(3): $\text{ord}(g^k) = (p-1)/\gcd(p-1, k)$. Это равно $p-1$ тогда и только тогда, когда $\gcd(p-1, k) = 1$. Таких $k$ ровно $\phi(p-1)$. $\square$

Нахождение примитивного корня

Алгоритм. Перебираем $g = 2, 3, 4, \ldots$ и для каждого проверяем: является ли $g$ примитивным корнем? Проверка:

Нужно убедиться, что $g^{(p-1)/q} \not\equiv 1 \pmod{p}$ для каждого простого делителя $q$ числа $p-1$.

Обоснование: $g$ является примитивным корнем тогда и только тогда, когда для каждого простого $q \mid (p-1)$ выполняется $g^{(p-1)/q} \not\equiv 1 \pmod{p}$. Действительно, если $\text{ord}(g) < p-1$, то $\text{ord}(g) \mid \frac{p-1}{q}$ для некоторого простого $q \mid p-1$, и тогда $g^{(p-1)/q} \equiv 1$.

Сложность. Факторизация $p-1$ требует $O(\sqrt{p})$

​) операций. Количество простых делителей $p-1$ — это $O(\log p)$. Каждая проверка — бинарное возведение в степень $O(\log p)$. Итого проверка одного кандидата: $O(\sqrt{p} + \log^2 p)$.

Эмпирически наименьший примитивный корень очень мал (чаще всего $\le 37$ для простых до $10^{18}$), поэтому на практике алгоритм работает быстро.

Задача дискретного логарифма

Задача DLP (Discrete Logarithm Problem). Дано простое $p$, примитивный корень $g$ и $b \in \mathbb{Z}_p^*$. Найти $x \in \{0, 1, \ldots, p-2\}$ такое, что $g^x \equiv b \pmod{p}$.

Это число $x$ называется индексом (или дискретным логарифмом) числа $b$ по основанию $g$ и обозначается $\log_g b$ или $\text{ind}_g b$.

Вычислительная сложность. Лучшие известные алгоритмы (индексное исчисление) работают за субэкспоненциальное время $L_p[1/3, c]$ для простого $p$. Для произвольных $p$ (2048-битных) задача на практике неразрешима. Для малых $p$ (до $10^{12}$ в задачах) применяется BSGS за $O(\sqrt{p})$

​).

Алгоритм Baby-step Giant-step (BSGS)

Рассмотрим задачу: найти $x$ такое, что $a^x \equiv b \pmod{p}$, где $0 \le x < p-1$.

Идея. Запишем $x = i \cdot m - j$, где $m = \lceil \sqrt{p} \rceil$

​⌉, $0 \le i \le m$, $0 \le j < m$. Тогда: $a^{im - j} \equiv b \pmod{p} \iff (a^m)^i \equiv b \cdot a^j \pmod{p}$

Алгоритм:

1. Baby steps: для $j = 0, 1, \ldots, m-1$ вычислить $b \cdot a^j \pmod{p}$ и сохранить в хэш-таблицу: значение $\to j$.
2. Giant steps: для $i = 1, 2, \ldots, m$ вычислить $(a^m)^i \pmod{p}$ и искать в хэш-таблице.
3. При нахождении совпадения: $x = i \cdot m - j$.

Корректность. Если решение существует, то для $x \in [0, p-1)$ можно представить $x = im - j$ с $1 \le i \le m$, $0 \le j < m$ (нужно убедиться, что все $x$ покрыты). При $m = \lceil\sqrt{p-1}\rceil$

​⌉ каждое $x \in [0, m^2)$ имеет разложение с $0 \le j < m$ и $1 \le i \le m$: берём $i = \lceil(x+1)/m\rceil$, $j = im - x$.

Сложность: $O(\sqrt{p})$

​) времени и $O(\sqrt{p})$ памяти.

Детали реализации:

• Хранить в map: (b * pow(a, j)) % p -> j
• При нескольких совпадениях брать наименьший $x$
• Обработать случай $b = 1$ отдельно (ответ $x = 0$)

Обобщённый BSGS (для составного модуля)

Задача: найти $x \ge 0$ такое, что $a^x \equiv b \pmod{m}$, где $m$ может быть составным.

Трудность: при составном $m$ элемент $a$ может не иметь обратного, и стандартный BSGS неприменим.

Идея. На первых шагах $\gcd(a^k, m)$ может расти. Сведём задачу к случаю, когда $\gcd(a^x, m) = \gcd(b, m)$.

Пусть $d_1 = \gcd(a, m)$. Если $d_1 \nmid b$, решений нет (т.к. $d_1 \mid a^x$ для $x \ge 1$, значит $d_1 \mid b$). Иначе разделим: задача $a^x \equiv b \pmod{m}$ эквивалентна $a^{x-1} \cdot \frac{a}{d_1} \equiv \frac{b}{d_1} \pmod{m/d_1}$.

Повторяем, пока $\gcd(a, m/d_1 \cdots) \ne 1$. После $k$ шагов получаем: $\frac{a^k}{D} \cdot a^{x-k} \equiv \frac{b}{D} \pmod{M}$ где $D = \prod d_i$, $M = m / D$, и $\gcd(a, M) = 1$. Теперь применяем стандартный BSGS к уравнению $a^{x-k} \equiv \frac{b}{D} \cdot \left(\frac{a^k}{D}\right)^{-1} \pmod{M}$.

Индексное исчисление (идея)

Для больших простых $p$ BSGS за $O(\sqrt{p})$

​) слишком медлен. Используется метод индексного исчисления:

1. Выбор факторной базы. Фиксируем набор $B = \{p_1, p_2, \ldots, p_t\}$ малых простых. Вычисляем $\log_g p_i$ для каждого $p_i \in B$.

2. Сбор соотношений. Для случайных $k$ вычисляем $g^k \pmod{p}$ и проверяем, является ли результат $B$-гладким (все простые делители $\le p_t$). Если $g^k \equiv \prod p_i^{e_i}$, то $k \equiv \sum e_i \log_g p_i \pmod{p-1}$.

3. Линейная алгебра. Решаем систему уравнений над $\mathbb{Z}_{p-1}$.

4. Вычисление конкретного логарифма. Для данного $b$ ищем $k$ такое, что $b \cdot g^k$ — $B$-гладкое.

Сложность: $L_p[1/2, 1]$ для выбора оптимального $t$. Современные алгоритмы (NFS) дают $L_p[1/3, \sqrt[3]{64/9}]$

​].

Ключевые формулы (сводная таблица)

Реализация на C++20 (с анализом сложности)

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

// ─── Бинарное возведение в степень ────────────────────────────────────────
long long power(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = (__int128)result * base % mod;
        base = (__int128)base * base % mod;
        exp >>= 1;
    }
    return result;
}

// ─── Нахождение примитивного корня по модулю p ────────────────────────────
// Сложность: O(sqrt(p) + phi_factors * log p)
long long primitive_root(long long p) {
    // Факторизация p - 1
    long long n = p - 1;
    vector<long long> factors;
    {
        long long tmp = n;
        for (long long i = 2; i * i <= tmp; i++) {
            if (tmp % i == 0) {
                factors.push_back(i);
                while (tmp % i == 0) tmp /= i;
            }
        }
        if (tmp > 1) factors.push_back(tmp);
    }

    // Перебираем кандидатов
    for (long long g = 2; g <= p; g++) {
        bool is_root = true;
        for (long long q : factors) {
            // Проверяем g^((p-1)/q) ≢ 1 (mod p)
            if (power(g, n / q, p) == 1) {
                is_root = false;
                break;
            }
        }
        if (is_root) return g;
    }
    return -1; // не должно достигаться
}

// ─── BSGS: a^x ≡ b (mod p), p — простое, gcd(a,p)=1 ──────────────────────
// Возвращает наименьший x >= 0, или -1 если решений нет
// Сложность: O(sqrt(p)) время и память
long long bsgs(long long a, long long b, long long p) {
    a %= p;
    b %= p;

    if (b == 1) return 0; // a^0 = 1
    if (a == 0) return b == 0 ? 1 : -1;

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

    // Baby steps: таблица b * a^j -> j
    unordered_map<long long, long long> table;
    table.reserve(m + 5);
    long long cur = b;
    for (long long j = 0; j < m; j++) {
        table[cur] = j;
        cur = (__int128)cur * a % p;
    }

    // Giant steps: вычисляем (a^m)^i
    long long am = power(a, m, p);
    cur = am;
    for (long long i = 1; i <= m + 1; i++) {
        auto it = table.find(cur);
        if (it != table.end()) {
            long long x = i * m - it->second;
            if (x >= 0) return x;
        }
        cur = (__int128)cur * am % p;
    }
    return -1;
}

// ─── Обобщённый BSGS: a^x ≡ b (mod m), m — произвольное ──────────────────
// Находит наименьший x >= 0
// Сложность: O(log^2(m) + sqrt(m))
long long extended_gcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) { x = 1; y = 0; return a; }
    long long x1, y1;
    long long g = extended_gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

long long mod_inverse(long long a, long long m) {
    long long x, y;
    long long g = extended_gcd(a, m, x, y);
    if (g != 1) return -1;
    return (x % m + m) % m;
}

long long generalized_bsgs(long long a, long long b, long long m) {
    a %= m; b %= m;
    if (b == 1 || m == 1) return 0;

    // Приводим к случаю gcd(a, m) = 1
    long long k = 0;
    long long D = 1; // накопленный делитель
    long long cur_mod = m;

    // Накапливаем: умножаем обе части на a, пока gcd(a, cur_mod) == 1
    while (true) {
        long long g = __gcd(a, cur_mod);
        if (g == 1) break;
        if (b % g != 0) return -1;
        b /= g;
        cur_mod /= g;
        D = (__int128)D * (a / g) % cur_mod;
        k++;
        if (D == b % cur_mod) return k; // a^k ≡ b (mod m) — проверяем
    }

    // Теперь gcd(a, cur_mod) = 1
    // Решаем a^y ≡ b * D^{-1} (mod cur_mod)
    long long inv_D = mod_inverse(D, cur_mod);
    if (inv_D == -1) return -1;
    long long b_new = (__int128)b * inv_D % cur_mod;

    long long step = (long long)ceil(sqrt((double)cur_mod)) + 1;

    unordered_map<long long, long long> table;
    table.reserve(step + 5);
    long long val = b_new;
    for (long long j = 0; j < step; j++) {
        table[val] = j;
        val = (__int128)val * a % cur_mod;
    }

    long long am = power(a, step, cur_mod);
    val = am;
    for (long long i = 1; i <= step + 1; i++) {
        auto it = table.find(val);
        if (it != table.end()) {
            long long y = i * step - it->second;
            if (y >= 0) return y + k;
        }
        val = (__int128)val * am % cur_mod;
    }
    return -1;
}

// ─── Вычисление порядка элемента a в Z*_p ─────────────────────────────────
// Сложность: O(sqrt(p) * log p)
long long element_order(long long a, long long p) {
    // Порядок делит p-1, перебираем делители
    long long n = p - 1;
    long long ord = n;

    // Факторизуем n
    vector<long long> factors;
    {
        long long tmp = n;
        for (long long i = 2; i * i <= tmp; i++) {
            if (tmp % i == 0) {
                factors.push_back(i);
                while (tmp % i == 0) tmp /= i;
            }
        }
        if (tmp > 1) factors.push_back(tmp);
    }

    // Делим ord на простые, пока можно
    for (long long q : factors) {
        while (ord % q == 0 && power(a, ord / q, p) == 1) {
            ord /= q;
        }
    }
    return ord;
}

// ─── Демонстрация ──────────────────────────────────────────────────────────
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    // Пример 1: нахождение примитивного корня
    long long p = 1000000007LL;
    long long g = primitive_root(p);
    cout << "Primitive root mod " << p << ": " << g << "\n";

    // Пример 2: дискретный логарифм
    // Найти x: 3^x ≡ 100 (mod 10^9+7)
    long long a = 3, b = 100;
    long long x = bsgs(a, b, p);
    cout << "3^x ≡ 100 (mod " << p << "): x = " << x << "\n";
    if (x != -1) {
        cout << "Verification: 3^" << x << " = " << power(a, x, p) << "\n";
    }

    // Пример 3: обобщённый BSGS (составной модуль)
    // 2^x ≡ 3 (mod 100)
    long long x2 = generalized_bsgs(2, 3, 100);
    if (x2 == -1) cout << "No solution for 2^x ≡ 3 (mod 100)\n";
    else {
        cout << "2^" << x2 << " ≡ " << power(2, x2, 100) << " (mod 100)\n";
    }

    // Пример 4: порядок элемента
    cout << "ord(3) mod " << p << " = " << element_order(3, p) << "\n";

    return 0;
}

Анализ сложности:

Разбор задачи 1 (простая)

Задача. Дано простое $p$ и число $a$ ($1 \le a < p$). Найти порядок $a$ в группе $\mathbb{Z}_p^*$.

Источник: Codeforces, базовый уровень.

Решение. Порядок элемента $a$ делит $p-1$. Факторизуем $p-1$ и применяем следующий алгоритм: начинаем с $\text{ord} = p-1$ и пытаемся как можно больше «урезать» его. Для каждого простого $q \mid p-1$: пока $a^{\text{ord}/q} \equiv 1 \pmod{p}$, делаем $\text{ord} \leftarrow \text{ord}/q$.

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

ll power(ll base, ll exp, ll mod) {
    ll res = 1; base %= mod;
    for (; exp; exp >>= 1) {
        if (exp & 1) res = (__int128)res * base % mod;
        base = (__int128)base * base % mod;
    }
    return res;
}

int main() {
    ll p, a;
    cin >> p >> a;

    ll n = p - 1;
    // Факторизация p-1
    vector<ll> primes;
    for (ll q = 2; q * q <= n; q++) {
        if (n % q == 0) {
            primes.push_back(q);
            while (n % q == 0) n /= q;
        }
    }
    if (n > 1) primes.push_back(n);

    ll ord = p - 1;
    for (ll q : primes) {
        while (ord % q == 0 && power(a, ord / q, p) == 1)
            ord /= q;
    }
    cout << ord << "\n";
    return 0;
}

Сложность: $O(\sqrt{p} + \omega(p-1) \log p)$

​+ω(p−1)logp), где $\omega$ — число различных простых делителей.

Разбор задачи 2 (средняя)

Задача. Codeforces 17E / подобная задача: дано $a$, $b$, $p$ (простое, $p \le 10^9$). Найти наименьшее неотрицательное $x$ такое, что $a^x \equiv b \pmod{p}$, или сообщить, что решений нет.

Решение. Прямое применение BSGS. Разберём тонкие случаи:

1. $a \equiv 0$: решение только если $b = 0$ (при $x \ge 1$) или $b = 1, x = 0$ (осторожно: $0^0$ неопределено, поэтому обычно $x \ge 1$).
2. $a \equiv 1$: решение только $x = 0$ если $b = 1$, иначе нет (если $b \ne 1$).
3. $\gcd(a, p) \ne 1$ при составном $p$: нужен обобщённый BSGS.

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

ll power(ll b, ll e, ll m) {
    ll r = 1; b %= m;
    for (; e; e >>= 1, b = (__int128)b*b%m)
        if (e & 1) r = (__int128)r*b%m;
    return r;
}

// BSGS: a^x ≡ b (mod p), p простое, 0 ≤ x < p
ll solve(ll a, ll b, ll p) {
    if (p == 1) return 0;
    b %= p;

    // Частные случаи
    if (power(a, 0, p) == b) return 0;  // x=0: 1 ≡ b

    ll m = (ll)ceil(sqrt((double)p)) + 1;
    unordered_map<ll, ll> T;
    T.reserve(1 << 20);
    T.max_load_factor(0.25);

    ll baj = b;
    for (ll j = 0; j < m; j++) {
        T[baj] = j;
        baj = (__int128)baj * a % p;
    }

    ll am = power(a, m, p), cur = am;
    for (ll i = 1; i <= m + 1; i++) {
        auto it = T.find(cur);
        if (it != T.end()) {
            ll x = i * m - it->second;
            return x;
        }
        cur = (__int128)cur * am % p;
    }
    return -1;
}

int main() {
    ll a, b, p;
    cin >> p >> a >> b;
    ll ans = solve(a % p, b % p, p);
    if (ans == -1) cout << "no solution\n";
    else cout << ans << "\n";
}

Подводные камни:

• unordered_map может быть медленным из-за коллизий хэшей. Настройка reserve и max_load_factor ускоряет работу.
• При $b = 0$ и $a \ne 0$ решений нет (так как $a^x \not\equiv 0$ при $\gcd(a,p)=1$).

Разбор задачи 3 (сложная — Div.1 D / ICPC-уровень)

Задача. Дано $n$ и простое $p$. Найти количество $x \in [0, p-1)$ таких, что $x^n \equiv x \pmod{p}$. А также для заданного $c$ подсчитать количество решений $x^n \equiv c \pmod{p}$.

Источник: Codeforces 1033E (упрощённый вариант), ICPC-региональные 2019.

Решение.

Сначала заметим: $x = 0$ всегда является решением $x^n \equiv 0$ и не является решением $x^n \equiv c$ при $c \ne 0$.

Для $x \ne 0$: запишем $x = g^k$, где $g$ — примитивный корень. Тогда $x^n \equiv c$ равносильно $g^{kn} \equiv g^m$ (где $c = g^m$), то есть $kn \equiv m \pmod{p-1}$.

Количество решений $kn \equiv m \pmod{p-1}$: уравнение $kn \equiv m \pmod{p-1}$ имеет решения тогда и только тогда, когда $\gcd(n, p-1) \mid m$. При этом оно имеет ровно $d = \gcd(n, p-1)$ решений по модулю $p-1$.

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

ll power(ll b, ll e, ll m) {
    ll r=1; b%=m;
    for(;e;e>>=1,b=(__int128)b*b%m) if(e&1) r=(__int128)r*b%m;
    return r;
}

ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }

// Расширенный НОД
ll extgcd(ll a, ll b, ll &x, ll &y) {
    if (!b) { x=1; y=0; return a; }
    ll x1,y1, g=extgcd(b,a%b,x1,y1);
    x=y1; y=x1-(a/b)*y1; return g;
}

ll primitive_root(ll p) {
    ll n = p-1;
    vector<ll> fs;
    for(ll i=2;i*i<=n;i++) if(n%i==0){fs.push_back(i);while(n%i==0)n/=i;}
    if(n>1) fs.push_back(n);
    for(ll g=2;;g++){
        bool ok=true;
        for(ll q:fs) if(power(g,(p-1)/q,p)==1){ok=false;break;}
        if(ok) return g;
    }
}

// discrete_log: найти ind_g(b) (дискретный логарифм b по основанию g mod p)
// Возвращает -1 если b не в <g>
ll discrete_log(ll g, ll b, ll p) {
    if (b == 1) return 0;
    ll m = (ll)ceil(sqrt((double)(p-1)))+1;
    unordered_map<ll,ll> T; T.reserve(m*2); T.max_load_factor(0.25);
    ll cur = b;
    for(ll j=0;j<m;j++){ T[cur]=j; cur=(__int128)cur*g%p; }
    ll gm=power(g,m,p); cur=gm;
    for(ll i=1;i<=m+1;i++){
        auto it=T.find(cur);
        if(it!=T.end()) return i*m - it->second;
        cur=(__int128)cur*gm%p;
    }
    return -1;
}

int main(){
    ll p, n;
    cin >> p >> n;

    ll g = primitive_root(p);
    ll d = gcd(n % (p-1), p-1);

    // Количество x: x^n ≡ x (mod p)
    // x=0: 1 решение
    // x≠0: x^(n-1) ≡ 1 (mod p) <=> ord(x) | gcd(n-1, p-1)
    ll d2 = gcd((n-1) % (p-1), p-1);
    cout << "x^n ≡ x solutions: " << d2 + 1 << "\n";

    // Количество решений x^n ≡ c для данного c
    ll c; cin >> c;
    if (c == 0) {
        cout << "x^n ≡ 0: 1 solution (x=0)\n";
    } else {
        ll m = discrete_log(g, c, p);
        // kn ≡ m (mod p-1): имеет d=gcd(n,p-1) решений если d|m
        if (m % d != 0) {
            cout << "x^n ≡ c: 0 solutions\n";
        } else {
            cout << "x^n ≡ c: " << d << " solutions\n";
        }
    }
    return 0;
}

Ключевые наблюдения:

1. Изоморфизм $\mathbb{Z}_p^* \cong \mathbb{Z}_{p-1}$ (через примитивный корень) сводит степенное уравнение к линейному.
2. Количество решений линейного сравнения $kn \equiv m \pmod{p-1}$ равно $\gcd(n, p-1)$ или 0.
3. Дискретный логарифм позволяет перейти в «логарифмическое пространство».

Задачи для самостоятельного решения

Типичные ошибки

1. Переполнение при умножении. При $p \approx 10^9$ произведение двух чисел может достигать $10^{18}$, что переполняет long long. Используйте __int128 или __int128_t для промежуточных вычислений: (__int128)a * b % p.
2. Ошибка в покрытии BSGS. При $x \in [0, p-1)$ и $m = \lceil\sqrt{p-1}\rceil$ нужно убедиться, что $i$ доходит до $m+1$ включительно, иначе некоторые $x$ могут быть пропущены.
3. Игнорирование $x = 0$. BSGS ищет $x \ge 1$. Всегда проверяйте $a^0 = 1 \equiv b$ отдельно.
4. Хэш-коллизии. unordered_map с int-ключами подвержен хэш-атакам. Используйте собственный хэш или reserve+max_load_factor.
5. BSGS для $a^x \equiv 0$. Если $\gcd(a, p) = 1$, то $a^x \ne 0$ никогда. Если $a \equiv 0 \pmod{p}$, то $a^x \equiv 0$ для всех $x \ge 1$.
6. Обобщённый BSGS: знак $x$. Ответ $x = im - j$ может оказаться отрицательным или нулём — нужно проверять $x \ge 0$.

Совет профессионала

Оптимизация хэш-таблицы. В соревнованиях unordered_map часто является узким местом BSGS. Рассмотрите альтернативы:

// Закрытая хэш-таблица с открытой адресацией — в 3-5 раз быстрее
struct HashMap {
    static const int MOD = (1 << 21); // степень двойки
    static const int MASK = MOD - 1;
    pair<long long, int> table[MOD];

    HashMap() { fill(begin(table), end(table), make_pair(-1LL, -1)); }

    void insert(long long key, int val) {
        int h = key & MASK;
        while (table[h].first != -1 && table[h].first != key)
            h = (h + 1) & MASK;
        table[h] = {key, val};
    }

    int find(long long key) {
        int h = key & MASK;
        while (table[h].first != -1 && table[h].first != key)
            h = (h + 1) & MASK;
        return table[h].first == key ? table[h].second : -1;
    }
};

Эта реализация даёт ускорение в 3–5 раз по сравнению со стандартным unordered_map.

Итог

Мы изучили структуру мультипликативной группы $\mathbb{Z}_p^*$ через призму примитивных корней. Основные результаты:

1. Примитивный корень существует для любого простого $p$, их ровно $\phi(p-1)$.
2. Нахождение примитивного корня достигается перебором кандидатов с проверкой $g^{(p-1)/q} \not\equiv 1$ для простых $q \mid p-1$.
3. Алгоритм BSGS решает задачу дискретного логарифма за $O(\sqrt{p})$ времени и памяти — это оптимальный алгоритм для малых $p$ (до $10^{12}$).
4. Обобщённый BSGS обрабатывает составные модули, сводя задачу к случаю $\gcd(a, m) = 1$.
5. Изоморфизм $\mathbb{Z}_p^* \cong \mathbb{Z}_{p-1}$ позволяет сводить мультипликативные задачи к аддитивным.

Дискретный логарифм — один из фундаментальных инструментов не только олимпиадной математики, но и современной криптографии. Освоив BSGS, вы получаете мощный инструмент для задач на подсчёт корней степенных уравнений, анализ структуры групп и решение задач с периодическими последовательностями.