MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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
share|cite|improve this question
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? – Gerry Myerson Jul 22 '12 at 12:21

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.

share|cite|improve this answer

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. . Then you can use Hensel's lifting and the Chinese remainder theorem to lift the solutions to $\mathbb Z/m\mathbb Z$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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