Solve multivariate equations in MATLAB/MAGMA/GP-PARI/SAGE

Question

I want to solve equations of the form $$a_1 x_1 + a_2 x_2 + a_3 x_3 + \dots + a_n x_n + b_1 x_1 x_2 + b_2 x_1 x_3 + \dots + b_n x_{n-1} x_n$$ where all the coefficients are in $GF(p)$ and variables are binary. Can you please tell me how do I solve this using MAGMA/MATLAB/SAGE/GP-PARI? Thanks in advance.

Answer 1

Working with multivariate and nonlinear polynomials, I'm not sure there is much built-in functionality to solve these. Of course, if there are not too many variables, you can just write a loop over the $2^n$ possibilities for the variables and check if each $n$-tuple is a solution. In Magma you can hard-code in your polynomial as a multivariate polynomial over $\mathrm{GF}(p)$ and then evaluate at each possible $n$-tuple of values for your variables.

I'm not sure your level of expertise in any of these languages, but in Magma for instance, it could be done in maybe five lines of code.

Answer 2

I've never used sage but see: sage groebner

To make a variable Boolean add the equation $x_k(1-x_k) = 0$