All geek questions in one place

Non-linear congruence solver (modular arithmetic)

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

In my specific case, the congruence is:

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.

+4
source share
2 answers

See Hansel's lemma .

+4
source

Yes, the common problem is NP-Complete.

This is because Boolean algebra is modulo 2 arithmetic! Thus, any 3SAT formula can be rewritten as an equivalent arithmetic expression in modulo 2 arithmetic. Checking the correctness of the 3SAT formula is equivalent to checking whether the corresponding arithmetic expression can be 1 or not.

For example, abb becomes ab in arithmetic. NOT a is 1-a etc.

But in your case, talking about NP-Compleness does not make sense, since this is one specific problem.

Also, lhf is correct. You can use the Hansel lifting lemma. The main point is that for the solution P(x) = 0 mod 2^(e+1) we can solve P(x) = 0 mod 2^e and "raise" these solutions to mod 2^(e+1)

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

+3
source

Source: https://habr.com/ru/post/1347819/

More articles:


All Articles