Усиление задачи дискретного логарифмирования

[ddn]

Задача дискретного логарифмирования (ДЛ) скорее всего является трудной, но скорее всего не является NP-полной. Но насколько далеко ей до полноты, а если ее усложнить?

Возмем систему целочисленных уравнений от ненулевых неизвестных $x_i$ с ненулевыми коэффициэнтами $a_{...}$ и $b_{...}$ "башенного" вида:
$b=g^{a_n \cdot x_n \cdot (g^{a_{n-1} \cdot x_{n-1} \cdot (g^{...^{a_1 \cdot x_1}} \mod p)} \mod p)} \mod p$,
где $p$ простое и $g$ его первообразный корень, хотя возможен вариант задачи без модуля. Это задачу назовем СБДЛ.

Каждое уравнение здесь имеет одну и ту же башенную высоту $n-1$ и порядок (неперестановочный) использования неизвестных $x_i$, уравнение можно записать как: $b=y_n$, где
$y_0=1$, $y_i=f(a_{i-1} \cdot x_{i-1}, y_{i-1})$ при $i=1..n$, $f(c,y)=g^{c \cdot y} \mod p$. Обратная функция к $f(c,y)$ по $y$ это дискретный логарифм. Нелинейность $f(c,y)$ по $y$ делает систему труднорешаемой.

При этом спутанность неизвестных $x_i$ друг с другом в одном уравнении имеет "последовательный" характер, только за счет нелинейности $f(c,y)$, при линейной $f(c,y)=c+y$ мы получили бы линейное уравнение.
В то время как в квадратичном диофантовом уравнении (КДУ) спутанность неизвестных $x_i$ друг с другом в одном уравнении имеет "паралельный" характер - гораздо сильнее:
$b=y_2=x_1 \cdot (a_{1,0} + a_{1,1} \cdot x_1 + ... + a_{1,n} \cdot x_n) + ... + x_n \cdot (a_{n,0} + a_{n,1} \cdot x_1 + ... + a_{n,n} \cdot x_n) \mod p$.
Видимо поэтому их система (СКДУ) дает NP-полную задачу (поиск одного из решений, если оно есть). Системы нелинейных диофантовом уравнении без такой спутанности, т.е. с уравнениями $b=a_1 \cdot x_1^{m_1} + ... + a_n \cdot x_n^{m_n} \mod p$, скорее всего не дают NP-полноты.

Предложенная задача СБДЛ при $n > 2$ не решается с помощью (не сводится полиномно к) ДЛ, она более общая (для задачи факторизации такого обобщения не сделать), значит можно предположить ее NP-полноту. Или, наоборот, "последовательная" (слабая) спутанность неизвестных $x_i$ делает такие задачи не NP-полными, для любой не NP-полной функции, обратной к $f(c,y)$ по $y$. Какие результаты или гипотезы об этом известны?

Более упрощенная задача - с одним уравнением и одним, заменяющем остальные, неизвестным: $b=g^{a_n \cdot x \cdot (g^{a_{i-1} \cdot x \cdot (g^{...^{a_1 \cdot x}} \mod p)} \mod p)} \mod p$. Она имеет промежуточную сложность между ДЛ и СБДЛ, но совсем специфична.

[makxsiq]

ddn в сообщении #1553529 писал(а):

Системы нелинейных диофантовом уравнении без такой спутанности, т.е. с уравнениями $b=a_1 \cdot x_1^{m_1} + ... + a_n \cdot x_n^{m_n} \mod p$, скорее всего не дают NP-полноты.

Спорный тезис.
На первый взгляд, частным случаем этой задачи является задача бинарного целочисленного программирования, одна из NP-полных задач Карпа

[ddn]

makxsiq в сообщении #1553623 писал(а):

ddn в сообщении #1553529 писал(а):

Системы нелинейных диофантовом уравнении без такой спутанности, т.е. с уравнениями $b=a_1 \cdot x_1^{m_1} + ... + a_n \cdot x_n^{m_n} \mod p$, скорее всего не дают NP-полноты.

Спорный тезис.
На первый взгляд, частным случаем этой задачи является задача бинарного целочисленного программирования, одна из NP-полных задач Карпа

Да, про задачу ЦП я и забыл, только ЦП без модуля.
Все таки, задача ЦП требует поиска "минимального" решения, а не любого. Хотя можно сдвигом одного неравенства "зажать" допустимую область и оставить одно решение - "минимальное", и такой класс задач ЦП все равно останется NP-полным.

Но главное, в ЦП имеется много неравенств, в том числе для переменных (неотрицательность), дающих главную сложность решения. Если в ЦП имеются только равенства, как и в моей задаче, то (в случае их совместности), для переменных легко находятся линейные параметрические решения со свободными параметрами и рациональными коэффициэнтами, и легко проверяется, может ли быть целое решение (этому могут помешать нецелые свободные члены в параметрических уравнениях).

То есть системы линейных диофантовых уравнений легко решаемы, иначе непонятно, почему квадратичные системы (СКДУ) приводятся как простейший пример NP-полных диофантовых задач. Задачи с неравенствами это другой класс задач и другой источник NP-полноты.

Дальше вопрос, насколько можно сузить класс СКДУ, чтобы он оставался NP-трудным или NP-полным - сколько минимально и каких должно быть ненулевых коэффициэнтов?: $m+1$, $2 \cdot m$, $n \cdot m$, $O(n^2)$ и т.д., где $m$ - число уравнений. Структура сцеплений тоже может иметь решающее значение, если системы с $b=a_1 \cdot x_1^{m_1} + ... + a_n \cdot x_n^{m_n}$ не NP-полные.

[makxsiq]

ddn в сообщении #1553656 писал(а):

Все таки, задача ЦП требует поиска "минимального" решения, а не любого.

Карп формулирует задачу только с ограничениями.
Входные данные: целочисленная матрица $C$ и целочисленный вектор $d$.
Задача: существует или нет 0-1 вектор $x$, такой что $Cx=d$.
http://cgi.di.uoa.gr/~sgk/teaching/grad ... s/karp.pdf
стр. 94

Эта задача из так называемого класса CSP (constraint satisfaction problems).
В книге "Mathematics and Computation" можно найти, что любая задача CSP либо в P, либо NP-полная.
https://www.math.ias.edu/avi/book

Цитата писал(а):

Every CSP is either in P or is NP-complete.