System of nonlinear equations mod 2

Question

Suppose I have unknown coefficients ${a_i}$, ${b_i} \in \mathbb{F_2}$ for $0 \le i \le n$

let $$s_k = \sum_{i+j=k}a_ib_j \mod 2$$

Then I would would like to solve system of equations (i.e. find all the $a$s and $b$s) given by $$s_0 = c_0$$ $$s_1 = c_1$$ $$...$$ $$s_{2n} = c_{2n}$$

where $c_i \in \mathbb{F}_2$

While I understand this can be done via factorization of $c = \sum_{0 \le i \le 2n}c_ix^i$, I am hoping for a more straightforward approach.

Answer 1

You can make a linear system of $n^2$ binary variables, one for each $v_{i,j} = a_ib_j$.

Then after solving for all $v_{i, j}$, we can make another linear system of inequalities, where $v_{i, j} \leq a_i +b_j \leq 2v_{i, j}$.