Решение системы булевых уравнений

[dnxx]

Всем добрый день.
Есть следующая система из 7 булевых уравнений с 8 неизвестными:
$ \parindent=0em b_0 = a_0 & a_4 \newline b_1 = a_0 & a_5 \oplus a_1 &a_4\newline b_2 = a_0 & a_6 \oplus a_1&a_5 \oplus a_2&a_4 \newline b_3 = a_0&a_7 \oplus a_1&a_6 \oplus a_2&a_5 \oplus a_3&a_4 \newline b_4 = a_1&a_7 \oplus a_2&a_6 \oplus a_3&a_5 \newline b_5 = a_2&a_7 \oplus a_3&a_6 \newline b_6 = a_3&a_7 \newline $

Задача состоит в том, чтобы найти все допустимые $a$, если $b$ известны (точнее алгоритм нахождения).
Очевидно, как мне кажется, что так как переменных на 1 больше чем уравнений, то следует зафиксировать одну из $a$ и найти все остальные. Однако дальше развить мысль не получается.

[demolishka]

Если вы пишите алгоритм для компьютера, то просто перебирать всевозможные комбинации. Иначе же можно исключать заведомо неправильные наборы. Например, если $b_0=1$, то рассматривать имеет смысл только наборы с $a_0=1$ и $a_4=1$.

[dnxx]

Да, это алгоритм для компьютера. И с большой долей вероятности перебор - не выход, так как одна из вариаций задачи имеет 512 переменных. Из того, что удалось установить:
1. Решение симметрично (то есть, если $a_0a_1a_2a_3a_4a_5a_6a_7$ - решение, то $a_4a_5a_6a_7a_0a_1a_2a_3$ тоже будет решением)
2. Уравнение имеет либо одну либо две пары решений
Исходя из этого, предполагаю, что существует форма записи системы, при которой задав одну из переменных можно вычислить все остальные.

[Deggial]

Очевидно, что данная задача суть разложение многочлена $B(x)=\sum\limits_{k=0}^{2n}b_kx^k$ на множители $A_1(x)=\sum\limits_{k=0}^na_kx^k$ и $A_2(x)=\sum\limits_{k=0}^na_{k+n+1}x^k$ над кольцом $\mathbb{Z}_2[x]$. Соответственно, ТС надо искать и программировать именно разложение многочлена на множители над $\mathbb{Z}_2[x]$.
Ясно, что $A_1(x), A_2(x)$ симметричны, а число решений равно в точности числу делителей $B(x)$. Тривиальные решения: $A_1(x)\equiv 1$. И т.п.

[Geen]

dnxx в сообщении #1007170 писал(а):

Уравнение имеет либо одну либо две пары решений

Например, $b_0=1,\;b_3=0,\;b_6=1$? Или все нули?

[dnxx]

Deggial, правильно ли я понял из вашего сообщения, что следует каждое уравнение исходной системы неким образом разбить на 2 уравнения, причем в первом неизвестными будут $a_0a_1a_2a_3$ а во втором $a_4a_5a_6a_7$? Если нет, то попрошу пояснить что имелось в виду? Также не понял утверждения про тривиальное решение $A_1(x)\equiv 1$. Почему это будет решением?

Geen в сообщении #1007185 писал(а):

Например, $b_0=1,\;b_3=0,\;b_6=1$? Или все нули?

Не понял вопроса

[Deggial]

dnxx в сообщении #1007193 писал(а):

Deggial, правильно ли я понял из вашего сообщения, что следует каждое уравнение исходной системы неким образом разбить на 2 уравнения, причем в первом неизвестными будут $a_0a_1a_2a_3$ а во втором $a_4a_5a_6a_7$?

Нет, нельзя. Просто Ваша задача изоморфна разложению многочлена на множители в $\mathbb{Z}_2[x]$.

dnxx в сообщении #1007193 писал(а):

Также не понял утверждения про тривиальное решение $A_1(x)\equiv 1$. Почему это будет решением?

Потому что $B(x)=(1+0x+0x^2+...)B(x)$.

dnxx в сообщении #1007193 писал(а):

Geen в сообщении #1007185 писал(а):

Например, $b_0=1,\;b_3=0,\;b_6=1$? Или все нули?

Не понял вопроса

Вам привели контрпример к Вашему утверждению. Число решений вообще не ограничено сверху.

[dnxx]

Всем привет. Сразу извинюсь за некропостинг, но пришлось вернуться к решению этой задачи, а новую тему создавать не хочется.
Итак, я осмыслил информацию уважаемого Deggial, и у меня остался один вопрос. Почему все же тривиальным решением будет $A_1(x)\equiv 1$ ?

Итак, имеем к примеру $B(x)=x^2 + x^3 + x^4 + x^5$, тогда если $A_1 = (1 + 0x + 0x^2 + 0x^3)$, то $A_2 = (0 + 0x + x^2 + x^3 + x^4 + x^5)$. Но для $A_1$ и $A_2$ должно быть $k < 4$. Значит ли это, что утверждение про тривиальное решение неверно? Или я чего то не понял?

[Brukvalub]

dnxx в сообщении #1044065 писал(а):

Значит ли это, что утверждение про тривиальное решение неверно? Или я чего то не понял?

Вы правильно поняли, это утверждение ошибочно. Из-за ограничений на степени сомножителей в некоторых случаях не всякий делитель исходного многочлена порождает решение системы.