비선형 합동 솔버 (모듈러 산술)

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 비평에 대해 이야기하는 것은 의미가 없습니다. 특정 문제이므로 말이됩니다.

또한 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)

에 그 솔루션을 해결하는 것입니다