非線性同餘求解器（模運算）

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