非线性同余求解器（模运算）

Question

有没有一种算法可以解决模运算中的非线性同余问题？我读到这样的问题被归类为NP完全。

在我的特定情况下，一致性的形式为：

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

其中a和b已知常量，我需要解决它对于x。

Answer 1

看看Hensel's lemma。

Answer 2

是的，一般问题是NP-Complete。

这是因为布尔代数是算术模2！因此任何3SAT公式可以被重写为算术模2中的等价算术表达式。检查3SAT公式是否可满足等同于检查相应的arithemetic表达式是否可以是1。

例如，AND b在arithemetic中变成a.b。 非a是1-a等

但在你的情况下，谈论NP补充没有意义，因为它是一个具体问题。

另外，lhf是正确的。可以使用Hensel的提升引理。基本的实质是要解决P(x) = 0 mod 2^(e+1)我们能够解决P(x) = 0 mod 2^e和“电梯”的解决方案，以mod 2^(e+1)

这里是一个PDF解释如何使用：http://www.cs.xu.edu/math/math302/04f/PolyCongruences.pdf