Solving binary equations using Grobner basis.

Question

I need help in solving binary equations using Grobner's basis. I have m equations with n variable of the form $$a_{11}\cdot x_1 + a_{12}\cdot x_2 + a_{13}\cdot x_3 + ....... + a_{1n}\cdot x_n = b_1$$ $$a_{21}\cdot x_1 + a_{22}\cdot x_2 + a_{23}\cdot x_3 + ....... + a_{2n}\cdot x_n = b_2$$ $$\vdots $$. $$a_{m1}\cdot x_1 + a_{m2}\cdot x_2 + a_{m3}\cdot x_3 + ....... + a_{mn}\cdot x_n = b_m$$ The variables $$x_i$$ is in binary and $$a_{ij},b_i \in GF(Q). m<n$$ I have got few references in some papers that this type of equations can be solved using Grobner basis and I need to know how. Is there any tools that I can use, for example magma, GP, sage etc. Your help will be highly appreciated.

Answer 1

I use grobner_basis in maxima http://maxima.sourceforge.net/

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

---

maxima example factoring 77:

load(affine);

grobner_basis( [(2^3*x3+2^2*x2+2*x1+1)*(2^3*y3+2^2*y2+2*y1+1)-77, x3+x2+x1-2, y3+y2+y1-2, y3^2-y3,y2^2-y2,y1^2-y1, x3^2-x3,x2^2-x2,x1^2-x1 ]);

(%o2)/R/ [(- 1) y3 + x2, (- 1) y2 + (- 1) x2 + 1, (- 1) y1 + 1,

                                                      2
                     (- 1) x3 + (- 1) x2 + 1, (- 1) x2  + x2, (- 1) x1 + 1]

---

This example is x*y = 77 split into bits of x and y.

$x = 2^3x_3 + 2^2x_2 + 2^1x_1 + 1$ , $y = 2^3y_3 + 2^2y_2 + 2^1y_1 + 1$

The Boolean conditions is enforced by the $x_k^2-x_k\ (= 0)$ equations.

Grobner Basis reduces the equations as far as it can.

The result line produced: $x_1 = 1, y_1=1, x_3 = 1 - x_2 , y_2 = 1 - x_2, y_3 = x_2$

$x = x_3 x_2 x_1 x_0 = \bar{x_2} x_211_2$ , $y = y_3 y_2 y_1 y_0 = x_2\bar{x_2}11_2$ (base 2).

So there is one undetermined variable $x_2$. Which makes seance since $77 = 7.11 = 11.7 = x.y$ so there are 2 solutions.

If $x_2 = 0$ then $x = 1011_2 = 11_{10}$ , $y = 0111_2 = 7_{10}$

If $x_2 = 1$ then $x = 0111_2 = 7_{10}$ , $y = 1011_2 = 11_{10}$

---

This example is: $$a_{11} x_1 + a_{12} x_2 - b_1\ (= 0)$$ $$a_{21} x_1 + a_{22} x_2 - b_2\ (= 0)$$

load(affine);

grobner_basis( [a11*x1 + a12*x2 - b1, a21*x1 + a22*x2 - b2, x2^2-x2,x1^2-x1 ]);

The output is quite long because of all the unknowns. Weeding out the interesting reductions:

x2 is isolated: $((- 1) b1 b2 + a21 b1) x2 + b1 b2 + (- 1) a21 b1 = 0$ note it does not assume b1 can be factored out.

x1 is isolated: $((- 1) b1 b2 + a22 b1) x1 + b1 b2 + (- 1) a22 b1 = 0$

There are many conditions on the constants $a_{jk}$ and $b_k$ as would be expected with Boolean $x_1,x_2$.

---

Numbers for constants:

$$2 x_1 + 3 x_2 - 3\ (= 0)$$ $$3 x_1 + 1 x_2 - 1\ (= 0)$$

load(affine);

grobner_basis( [2*x1 + 3*x2 - 3, 3*x1 + 1*x2 - 1, x2^2-x2,x1^2-x1 ]);

$[(- 1) x2 + 1, (- 1) x1]$

$x_1 = 0$ and $x_2 = 1$

---

No solution example:

$$2 x_1 + 3 x_2 - 3\ (= 0)$$ $$3 x_1 + 1 x_2 - 5\ (= 0)$$

load(affine);

grobner_basis( [2*x1 + 3*x2 - 3, 3*x1 + 1*x2 - 5, x2^2-x2,x1^2-x1 ]);

There is a constant (8 . 49) in the poly-simplifications.

                             [1]

It arrived at $1 = 0$ which is a contradiction so there are no solutions.

---