# Solve system of logical equations

I need a general method for solving systems of logical equations like: $$\begin{equation*} \begin{cases} c_{0} = a_{0} \land b_{0}\\\\ c_{1} = a_{0} \land b_{1} ⊕ a_{1} \land b_{0}\\\\ c_{2} = a_{0} \land b_{2} ⊕ a_{1} \land b_{1} ⊕ a_{2} \land b_{0}\\\\ c_{3} = a_{1} \land b_{2} ⊕ a_{2} \land b_{1}\\\\ c_{4} = a_{2} \land b_{2} \end{cases} \end{equation*}$$ Where c is known and a and b are unknown variables. This system is a system of logical nonlinear equations, I want to know if it is possible to find a general solution for such a system. The number of unknowns is 1 more than the number of equations. Solutions will be symmetric (a and b can be swapped). The challenge is not unsolvable and there is an example of a solution . However, it seems to me that there is a simpler solution.

## 1 Answer

Let $$A=a_0+a_1x+a_2x^2\cdots+a_nx^n$$, $$B=b_0+b_1x+\cdots+b_mx^m$$, and $$C=AB=c_0+\cdots+c_{n+m}x^{n+m}$$, where arithmetic occurs over $$\mathbb{F}_2$$. Then your problem is exactly equivalent to recovering $$\{A,B\}$$ from $$C$$. This is the problem of factorization of polynomials over finite fields. Although, remarkably, the factors can be computed in polynomial time, I don't there there are any particularly simple algorithms for doing so.