4
$\begingroup$

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

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ 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. $\endgroup$
    – Emil Jeřábek
    Aug 11, 2018 at 9:57
  • 1
    $\begingroup$ @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. $\endgroup$
    – KConrad
    Aug 11, 2018 at 11:53
  • $\begingroup$ Polynomial time polynomial factoring gives polynomial time in $\ell$ - not in $log(\ell)$ - which is not polynomial time in the input length. $\endgroup$
    – Dror Speiser
    Aug 12, 2018 at 18:29
  • $\begingroup$ @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. $\endgroup$
    – Emil Jeřábek
    Aug 12, 2018 at 18:36
  • $\begingroup$ @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$? $\endgroup$
    – Dror Speiser
    Aug 12, 2018 at 18:41

1 Answer 1

Reset to default
-1
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ Where can one read on the hinted equivalence of the two problems? Are they polynomialy reducible to each other? $\endgroup$
    – Dror Speiser
    Aug 12, 2018 at 18:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.