Given integers $a,\ell$ and prime $p$ we need to find the roots of the algebraic equation $x^\ell\equiv a\bmod p$. We know there are at most $\ell$ such $x$.

What is the best method to find all such $x$?

What is the complexity (is it $O(poly(\ell\log p)$?)?

randomizedpolynomial-time algorithms for factoring of polynomials over finite fields, your problem is a special case of that. Efficientdeterministicalgorithms are an open problem already for square root computation. – Emil Jeřábek Aug 11 at 9:57