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