Solving an arbitrary polynomial in $Z_m$

Question

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

Answer 1

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

Answer 2

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.