CODEWITHSUNDEEP
math
Ledio Berdellima
Ledio Berdellima

Reputation: 393

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 constants and I need to solve it for x.

Upvotes: 4

Views: 3659

Answers (2)

user127.0.0.1
user127.0.0.1

Reputation: 1337

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

Upvotes: 4

lhf
lhf

Reputation: 72312

Look at Hensel's lemma.

Upvotes: 5

Related Questions