Есть ли алгоритм, который может решить нелинейную конгруэнтность в модульной арифметике? Я читал, что такая проблема классифицируется как NP-complete.Нелинейный решатель конгруэнтности (модульная арифметика)
В моем конкретном случае конгруэнтность имеет вид:
x^3 + ax + b congruent to 0 (mod 2^64)
где а и Ь известны постоянные и мне нужно решить для х.
Посмотрите на Hensel's lemma.
Да, общая проблема NP-Complete.
Это потому, что булева алгебра является арифметической по модулю 2! Таким образом, любая формула 3SAT может быть переписана как эквивалентное арифметическое выражение в арифметике по модулю 2. Проверка правильности формулы 3SAT эквивалентна проверке того, может ли соответствующее арифметическое выражение быть 1 или нет.
Например, a b b становится a.b в arithemetic. NOT a is 1-a и т. Д.
Но в вашем случае говорить о NP-Compleness не имеет смысла, поскольку это одна конкретная проблема.
Кроме того, lhf является правильным. Лемма Хенселя может быть использована. Основная суть заключается в том, что для решения 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