Non-linear congruence solver (modular arithmetic)

Is there an algorithm that can solve a non-linear congruence in modular arithmetic? I read that such a problem is classified as NP-complete.

In my specific case the congruence is of the form:

x^3 + ax + b congruent to 0 (mod 2^64)

where a and b are known cons开发者_高级运维tants and I need to solve it for x.

Look at Hensel's lemma.

Yes, the general problem is NP-Complete.

This is because boolean algebra is arithmetic modulo 2! So any 3SAT formula can be rewritten as an equivalent arithmetic expression in arithmetic modulo 2. Checking if a 3SAT formula is satisfiable becomes equivalent to checking if the corresponding arithemetic expression can be 1 or not.

For example, a AND b becomes a.b in arithemetic. NOT a is 1-a etc.

But in your case, talking about NP-Compleness makes no sense, as it is one specific problem.

Also, lhf is right. Hensel's Lifting lemma can be used. The basic essence is that to solve P(x) = 0 mod 2^(e+1) we can solve P(x) = 0 mod 2^e and 'lift' those solutions to mod 2^(e+1)

Here is a pdf explaining how to use that: http://www.cs.xu.edu/math/math302/04f/PolyCongruences.pdf