有沒有一種算法可以解決模運算中的非線性同餘問題?我讀到這樣的問題被歸類爲NP完全。非線性同餘求解器(模運算)
在我的特定情況下,一致性的形式爲:
x^3 + ax + b congruent to 0 (mod 2^64)
其中a和b已知常量,我需要解決它對於x。
有沒有一種算法可以解決模運算中的非線性同餘問題?我讀到這樣的問題被歸類爲NP完全。非線性同餘求解器(模運算)
在我的特定情況下,一致性的形式爲:
x^3 + ax + b congruent to 0 (mod 2^64)
其中a和b已知常量,我需要解決它對於x。
是的,一般問題是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