# Solving a polynomial modulo an integer

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.

Without loss of generality we may assume $F$ is irreducible since otherwise we can just factor $F=f_0\cdots f_1$ with $f_i$ irreducible and the solutions of $F$ will be the union of the solutions for all of the $f_i$.

One method similar to Hensel lifting I've already considered roughly 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$ was a large prime though.

So any of the following would be very useful:

• Fast solutions for when $m$ is prime
• Methods to prove there are no solutions
• Any relevant research
-
For primes, and $x^m \equiv a$, there are fast methods for determining whether there is a solution. And there can be fast deterministic methods for some classes of primes and some $m$, and usually fast probabilistic methods for the others. –  André Nicolas Jul 19 '12 at 6:30
If $m$ is not a prime then a product can have more zeroes than the union of those of its factors. –  WimC Jul 19 '12 at 6:42

There is a nice randomized algorithm for finding the roots when $m=p$ is prime, it goes roughly as follows: first compute $$G(x) = \operatorname{gcd}\bigl( x^p-x,F(x)\bigr)$$ then $G(x)$ is the product of all the roots of $F(x)$ that are in $\mathbb Z/p$. Now for several random values of $a$ compute $$\operatorname{gcd}\bigl( (x+a)^{(p-1)/2}-1,G(x)\bigr)$$ this will probably result on a non trivial factor of $G$, because it separates roots $\alpha$ for which $x+a$ is a quadratic residue from those which are not. You can repeat with the resulting factors until all the factors have degree one. This algorithm is very fast. It is described here.