Discrete Logarithm

Solve $a^x\equiv b(\mathrm{mod}m)$ for $x$. Believed hard in general — which is exactly why Diffie-Hellman and ElGamal are built on it.

Baby-step giant-step — $O(\sqrt{m})$

Write $x=np-q$ with $n=\lceil \sqrt{m}\rceil$ and $0\le q<n$. Then

$a^{np}\equiv b{a}^q(\mathrm{mod}m).$

Precompute all $b{a}^q$ in a hash table (baby steps), then try each $a^{np}$ (giant steps).

// smallest x >= 0 with a^x = b (mod m); requires gcd(a, m) = 1
long long bsgs(long long a, long long b, long long m) {
    a %= m; b %= m;
    long long n = (long long)sqrtl((long double)m) + 1;
    unordered_map<long long,long long> vals;
    long long cur = b;
    for (long long q = 0; q <= n; q++) {              // baby steps: b * a^q
        vals[cur] = q;
        cur = cur * a % m;
    }
    long long an = powmod(a, n, m);
    cur = 1;
    for (long long p = 1; p <= n; p++) {              // giant steps: a^(n*p)
        cur = cur * an % m;
        auto it = vals.find(cur);
        if (it != vals.end()) {
            long long x = n * p - it->second;
            if (x >= 0) return x;
        }
    }
    return -1;
}

Insert baby steps in increasing $q$ so that overwriting keeps the smallest exponent, giving the minimal $x$.

Cost: $O(\sqrt{m})$ time and $O(\sqrt{m})$ memory. The memory is the binding constraint for $m\approx 10^{18}$.

When $\gcd (a,m)\ne 1$

Divide out the common factor repeatedly:

long long bsgsGeneral(long long a, long long b, long long m) {
    long long g, k = 0, add = 1;
    while ((g = __gcd(a, m)) > 1) {
        if (b == add) return k;
        if (b % g) return -1;                          // no solution
        b /= g; m /= g; add = add * (a / g) % m;
        k++;
    }
    long long r = bsgs(a, b * modinv(add, m) % m, m);
    return r == -1 ? -1 : r + k;
}

Each step removes a prime factor shared by $a$ and $m$, so the loop runs $O(\log m)$ times.

The method table

Method	Time	Space	Requires
Brute force	$O(m)$	$O(1)$	nothing
Baby-step giant-step	$O(\sqrt{m})$	$O(\sqrt{m})$	nothing
Pollard’s kangaroo	$O(\sqrt{b-a})$	$O(1)$	$x$ in a known interval
Pollard’s rho for DLP	$O(\sqrt{m})$	$O(1)$	nothing
Pohlig-Hellman	$O(\sum e_i\sqrt{p_i})$	small	$\phi (m)$ smooth
Index calculus	sub-exponential	large	${\mathbb{F}}_p^{\ast }$ only

Pohlig-Hellman is the important one: if the group order factors into small primes, the discrete log becomes easy. This is why cryptographic groups always use a prime or near-prime order.

Uses in competitive programming

Problem	Formulation
$a^x\equiv b(\mathrm{mod}p)$	directly
Find the period of a sequence $x_{i+1}=a{x}_i\mathrm{mod}m$	order of $a$
“After how many steps does the state repeat?“	discrete log in a cyclic structure
$x^k\equiv a$	discrete root — reduce via a primitive root
Solve a linear recurrence’s period	order of the transition matrix
Matrix discrete log $A^x=B$	BSGS with matrix multiplication and hashing

The matrix generalisation is worth knowing: BSGS works in any group where you can multiply and hash elements, so $A^x=B$ for matrices is solvable in $O(\sqrt{m}\cdot n^3)$ by the identical algorithm.

Practical notes

• Use a fast hash map (gp_hash_table or a hand-rolled open-addressing table) — unordered_map with $10^5$ insertions is often the bottleneck, and its default hash is hackable.
• Sorting a vector and binary searching is a fine alternative: $O(\sqrt{m}\log m)$ but with a much smaller constant and better memory behaviour.
• Watch for $b\equiv 1$ (answer 0) and $a\equiv 0$ as special cases.

See also: Primitive Root · Pohlig-Hellman · Pollard Kangaroo