1
$\begingroup$

Say I have a polynomial $F$ of degree $n$ with coefficients in $Z_m$ and I wish to find $x$ such that $F(x)=0$ (mod $m$). For instance if $F(x)=x^{2}-a$ the solution would be the modulo $m$ squareroot of $a$ (if there is a solution).

I'm primarily interested in solving the general case. We can assume $F$ and $m$ may be factored "easily."

One method similar to Hensel lifting I've already roughly considered would involve factoring $m=p_0^{a_0}\cdots p_k^{a_k}$ and brute forcing $x$ (mod $p_i$) for each $i$ and lifting them to solutions mod $p_i^{a_i}$. This would be problematic if $m$ contains a large prime power however.

So any of the following would be very useful:

  • Fast algorithms for when $m=p^k$ is large
  • Methods to prove there are no solutions
  • Any proofs or conjectures that would indicate efficient algorithms cannot exist
  • Any relevant research
$\endgroup$
2
  • 4
    $\begingroup$ You write that we can assume $F$ can be factored easily. I'm not sure what you mean. If you can factor $F$ easily into linear factors, the problem solves itself, right? $\endgroup$ Jul 22, 2012 at 12:21
  • $\begingroup$ Coming up to ten years, and still no clarification. $\endgroup$ May 17, 2022 at 7:51

2 Answers 2

3
$\begingroup$

Instead of brute force, irreducibility testing of polynomials over any finite field (in particular, $\mathbb Z/p\mathbb Z$ with $p$ prime) can be done in deterministic polynomial time, and factoring of polynomials over finite fields is possible in randomized polynomial time. See e.g. http://en.wikipedia.org/wiki/Factorization_of_polynomial_over_finite_field_and_irreducibility_tests . Then you can use Hensel's lifting and the Chinese remainder theorem to lift the solutions to $\mathbb Z/m\mathbb Z$.

$\endgroup$
3
$\begingroup$

The first question is do you know the factoring of $m$?

If yes than using Chinese Reminder Theorem it is enough for you to solve it only for $p^k$. For $p^k$ you can use Hensel lifting its comlexity is $O(k\log{p} \mathrm{polylog}(k\log p))$ i.e., up to poly-logarithmic factor it is optimal.

If no than your problem is equivalent to factoring.

$\endgroup$

Your Answer

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

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