solution of a system of equations in algebraic closure of GF2

Question

I have a set of equations and I want to know whether there exist solutions of these equations in an extension of Galois field $\mathbb{GF}_2$ and what are they? Is there a procedure to check this? For example, the following set of equations in variables ${a,b,c,d,e,f}$ $1 + a + c + e = 0, b + d + f = 0, 1 + a e + c e + a c = 0, b e + a f + c f + e d + b c + a d = 0, b f + f d + b d = 0$ have the solution $a=1,b=1,c=1,d=\omega,e=1,f=\omega^2$ which lie in an extension of $\mathbb{GF}_2$, $\mathbb{GF}_4= \frac{\mathbb{GF}_2[u]}{u^2+u+1}$ where $\mathbb{GF}_2[u]$ is a polynomial ring with variable $u$ and one representation of $\mathbb{GF}_4$ is ${0,1,\omega,\omega^2}$.

Answer 1

By Hilbert's Nullstellensatz the set of common zeros of those polynomials in the algebraic closure is empty if and only if the constant polynomial 1 is in the ideal $I$ they generate in the ring of polynomials $R$. Actually this is exactly what the weak Nullstellensatz states, and that suffices here. In your example case $R=GF(2)[a,b,c,d,e,f]$ is the ring of polynomials in the listed six variables, and $$I=\langle 1 + a + c + e , b + d + f, 1 + a e + c e + a c, b e + a f + c f + e d + b c + a d, b f + f d + b d\rangle.$$

The question whether $1\in I$ or not can be decided algorithmically by first generating a Gröbner basis of the ideal, and then checking whether there are non-zero constants in the Gröbner basis. Several computer algebra packages include an implementation Buchberger's algorithm (or something more efficient) that produces a Gröbner basis of $I$ given any set of generators.