$(n,p-1) = g > 2$, where our goal is to solve $x^n = b \pmod{p}$. By utilizing the Euclidean algorithm we can reduce it to $x^g = a \pmod{p}$. What is the best way to solve $x^g = a \pmod{p}$? We can't reduce $g$ anymore. Is the only way to solve for all such that $x^g = a \pmod{p}$ by plugging in all ${1,2,...,p-1}$?
For example, $x^6 = 1 \pmod{19}$.
Although the Tonelli–Shanks algorithm (which handles the case $g=2$) can be extended to higher values of $g$ (most naturally prime ones), the technique used in practice (as far as I know) is random splitting, more generally for solving arbitrary polynomial equations $f(x)=0$ over $\mathbb{F}=\mathbb{Z}/p\mathbb{Z}$ (of not a huge degree).
The idea is simple. If the degree is $<3$, solve it the usual way (using the T-S for square roots). Otherwise take $a\in\mathbb{F}$ at random, and compute $g(x)=\gcd\big(f(x),(x-a)^{(p-1)/2}-1\big)$ over $\mathbb{F}$ (i.e., in $\mathbb{F}[x]$). With high probability, $g(x)$ will be non-trivial; once it is, recurse for $g(x)$ and $f(x)/g(x)$.
With an arbitrary $f(x)$ in the beginning, a setup step $f(x)\gets\gcd\big(f(x),x^p-x\big)$ is done to cast out factors which are irreducible over $\mathbb{F}$; for our case $f(x)=x^g-a$ with $g\mid p-1$, this is not needed (assuming we've checked that $f$ has roots, i.e. that $a^{(p-1)/g}=1$).
In all cases, $\gcd(f,u^n-v)$ is computed (with whatever version of the Euclidean algorithm) after initial reduction of $u^n-v$ modulo $f$, which is done using fast exponentiation in $\mathbb{F}[x]/(f)$.