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)$?)?

bumped to the homepage by Community 2 days ago

This question has answers that may be good or bad; the system has marked it active so that they can be reviewed.

  • 1
    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
  • 1
    @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).

  • 3
    Where can one read on the hinted equivalence of the two problems? Are they polynomialy reducible to each other? – Dror Speiser Aug 12 at 18:27

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.