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.