# Higher roots modulo prime complexity best algorithm

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$.

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

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

• There are randomized polynomial-time algorithms for factoring of polynomials over finite fields, your problem is a special case of that. Efficient deterministic algorithms are an open problem already for square root computation. – Emil Jeřábek Aug 11 at 9:57
• @EmilJeřábek saying efficient deterministic square root calculations mod $p$ are "an open problem" and nothing more about them is not telling the whole story, since it might suggest there is no idea what such an algorithm might look like. The paper of Adleman, Manders, and Miller at cs.cmu.edu/~glmiller/Publications/AMM77.pdf provides such an algorithm (for square roots) under GRH for Dirichlet $L$-functions. – KConrad Aug 11 at 11:53
• Polynomial time polynomial factoring gives polynomial time in $\ell$ - not in $log(\ell)$ - which is not polynomial time in the input length. – Dror Speiser Aug 12 at 18:29
• @DrorSpeiser This depends on whether you write $\ell$ in unary or in binary, but in any case, polynomial in $\ell$ is exactly what the OP asks for. – Emil Jeřábek Aug 12 at 18:36
• @EmilJeřábek True that. I think the OP is asking what the best method is, and whether the complexity is a particular one. But maybe I misunderstood your comment: are randomized polynomial factoring algorithms, that take $poly(\ell log(p))$ time, the best known? With no dependence on $\ell$? – Dror Speiser Aug 12 at 18:41

This is essentially the same question as that of finding primitive roots mod $p,$ and this is discussed at length in Ofer Grossman's nice report (2015).