Factorizing multivariate polynomials in $GF_2[x_1, ..., x_n]/[x_1+x_1^2,...]$

Question

I'm trying to factorize multivariate polynomials in the quotient ring $GF_2[x_1, ..., x_n]/[x_1+x_1^2,...,x_n+x_n^2]$.

For example $$ \begin{align} f&=(x_1 + x_2 + x_3)(x_2 + x_4)(x_1 + x_4) \\ &=x_1^2x_2+x_1x_2^2+x_1x_2x_3+x_1^2x_4+x_2^2x_4+x_1x_3x_4+x_2x_3x_4+x_1x_4^2+x_2x_4^2+x_3x_4^2 \tag{1}\label{eq1} \\ &= x_1x_2x_3 + x_1x_3x_4 + x_2x_3x_4 + x_3x_4 \tag{2}\label{eq2} \end{align} $$

$\eqref{eq2}$ is the result of applying the quotient.

Sage Math allows me to factor polynomials like $\eqref{eq1}$ quite well, but not polynomials like $\eqref{eq2}$. Indeed in the case of $\eqref{eq2}$, all it produces is $x_3(x_1x_2 + x_1x_4 + x_2x_4 + x_4)$ whereas I would like to get all the linear factors as seen in the original poly. I'm not sure if this is simply a local optimum that it found, and maybe it could be coerced into looking specifically for only linear factors?

Is there an algorithm that is applicable specifically to factoring these sorts of polys (as seen in $\eqref{eq2}$) into linear factors? I've started looking into Lenstra (1984) and Bernardin (1999) which seem promising, but will take me a while due to my limited math experience, so a pointer in the right direction would be great!

Answer 1

It's not particularly difficult to produce an inefficient algorithm to solve this problem. For specific polynomials in a small (couple of dozen?) number of variables this isn't too hard. Let the number of variables be $n$, and let $f$ be the polynomial you need to factorize.

1. Enumerate all linear equations. There are $2^{n-1}$ of these. Call this set $X$.
2. For each $p\in X$, form the ideal $I_p=\langle p,x_i^2+x_i\rangle$. Use your CAS to produce a Groebner basis for this ideal so you can test membership.
3. For each $p$, check if $f\in I_p$. If it is, then there exists $g_p$ such that $f=p g_p$ modulo the relations $x_i^2+x_i$.
4. Use recursion to describe all possibilities.

Now Magma (possibly other CASes) allows you to write $f$ as an member of $I_p$ whenever $f$ lies in it. Perhaps a better alternative is:

4. Now you know all $p$ such that $p\mid f$ in this ring, just multiply them together in all ways to see which subsets of them multiply to $f$. It's probably faster than recursion.