非線形合同ソルバー（モジュラ演算）

Question

モジュラ演算で非線形合同を解くアルゴリズムはありますか？私はそのような問題はNP完全と分類されると読んでいます。 aとbは定数を知られている

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

と私は、xのためにそれを解決する必要があります：私の特定の場合には

合同の形式です。

Answer 1

Hensel's lemmaをご覧ください。

Answer 2

はい、一般的な問題はNP完全です。

これは、ブール代数が2を法とするためです。したがって、3SATの式は、2を法とする算術式で同等の算術式として書き直すことができます.3SATの式が充足可能かどうかを確認することは、対応する表現式が1であるかどうかをチェックすることと等価です。

たとえば、AND bは、arithemeticではa.bになります。 NOT aは1-aなどです。

あなたのケースでは、NP準拠について話すことは、特定の問題の1つではありません。

また、lhfが正しいです。ヘンゼルの持ち上げ補助定理を使うことができます。 http://www.cs.xu.edu/math/math302/04f/PolyCongruences.pdf

：基本的な本質は、それはPDFがそれを使用する方法を説明している私たちが P(x) = 0 mod 2^e解決することができ P(x) = 0 mod 2^(e+1)と「リフト」ここ mod 2^(e+1)

にこれらのソリューションを解決することです