Discrete Root

Solve $x^k\equiv a(\mathrm{mod}n)$ — find all $k$-th roots of $a$.

The prime case, via a primitive root

Let $g$ be a primitive root modulo $p$. Write $x=g^y$ and $a=g^{\mathrm{ind}(a)}$. Then

$x^k\equiv a⟺ky\equiv \mathrm{ind}(a)(\mathrm{mod}p-1),$

which is an ordinary linear congruence.

Algorithm

1. Find a primitive root $g$ modulo $p$.
2. Compute $\mathrm{ind}(a)={\log }_{g}a$ with baby-step giant-step, $O(\sqrt{p})$.
3. Solve $ky\equiv \mathrm{ind}(a)(\mathrm{mod}p-1)$. Let $d=\gcd (k,p-1)$:
   • if $d\nmid \mathrm{ind}(a)$ → no solution;
   • otherwise there are exactly $d$ solutions $y_0+j\frac{p-1}{d}$.
4. Each gives a root $x_j=g^{y_j}\mathrm{mod}p$.

vector<long long> discreteRoots(long long k, long long a, long long p) {
    if (a == 0) return {0};
    long long g = primitiveRoot(p);
    long long ia = bsgs(g, a, p);                       // index of a
    if (ia < 0) return {};
    long long d = __gcd(k, p - 1);
    if (ia % d) return {};
    long long mod = (p - 1) / d;
    long long y0 = (__int128)(ia / d) * modinv(k / d, mod) % mod;
    vector<long long> res;
    long long step = powmod(g, mod, p), cur = powmod(g, y0, p);
    for (long long j = 0; j < d; j++) { res.push_back(cur); cur = cur * step % p; }
    sort(res.begin(), res.end());
    return res;
}

Cost: $O(\sqrt{p})$, dominated by the discrete log.

The count

There are either 0 or exactly $\gcd (k,p-1)$ roots. And $a$ is a $k$-th power residue iff

$a^{\frac{p-1}{\gcd (k,p-1)}}\equiv 1(\mathrm{mod}p).$

For $k=2$ this is the Euler criterion.

Special cases worth shortcutting

Case	Shortcut
$\gcd (k,p-1)=1$	exactly one root: $x=a^{k^{-1}\mathrm{mod}(p-1)}$ — no discrete log needed
$k=2$	Tonelli-Shanks or Cipolla, $O({\log }^{2}p)$
$k=2$, $p\equiv 3(\mathrm{mod}4)$	$x=a^{(p+1)/4}$
$a=0$	the only root is $x=0$
$a=1$	the $\gcd (k,p-1)$ roots of unity

The first row is the one people miss: when $k$ is coprime to $p-1$, the $k$-th root is just a modular exponentiation with the inverse exponent. Check that before reaching for BSGS.

Composite moduli

$x^k\equiv a(\mathrm{mod}n)$ with $n=\prod p_i^{e_i}$:

1. Factor $n$.
2. Solve $x^k\equiv a(\mathrm{mod}{p}_i)$ for each prime.
3. Hensel lift each solution to $p_i^{e_i}$ (the derivative $k{x}^{k-1}$ must be a unit — care needed when $p\mid k$).
4. Recombine every combination with the CRT.

The number of solutions is the product over prime powers, which can be large. $p=2$ needs special handling because $k{x}^{k-1}$ is never a unit there.

Cube roots and beyond

Nothing special is needed for $k=3$ or larger — the primitive-root reduction handles all $k$ uniformly. The only reason $k=2$ has dedicated algorithms is that quadratic residues are common enough to deserve an $O({\log }^{2}p)$ method instead of $O(\sqrt{p})$.

Related problems

Problem	Method
$x^k\equiv a(\mathrm{mod}p)$	this page
$a^x\equiv b(\mathrm{mod}m)$	discrete log
$x^2\equiv a(\mathrm{mod}p)$	Tonelli-Shanks
Count $k$-th power residues	$\frac{p-1}{\gcd (k,p-1)}$
$x^k\equiv a(\mathrm{mod}{p}^e)$	solve mod $p$, then Hensel
Is $a$ a perfect $k$-th power in $\mathbb{Z}$?	integer $k$-th root, not modular

See also: Primitive Root · Discrete Logarithm · Quadratic Residues