Decomposing a polynomial over GF(2) into sparse factors mod $x^{2^k}$

Question

There is a lot of work on decomposing these polynomials to irreducible factors without the modulo $x^{2^k}$ part. That doesn't really work for this problem (apart from giving some upper bound on the sparseness) because the modulo $x^{2^k}$ effectively allows dividing anything by any polynomial that has $1$ in it, so divisibility tests don't work: everything is divisible by anything that matters. Also I don't care about irreducibility, but I do care about sparseness, and no decomposition algorithm that I could find takes that into account.

For the sparseness, what I want to minimize is the total count of non-zero coefficients while disregarding the constant $1$ in factors. So $x + 1$ has a "cost" of 1, and $(x^2 + 1)(x^7 + x^4 + 1)$ has a "cost" of 3.

Sometimes the common algorithms work, $x^7+x^6+x^5+x^4+x^3+x^2+x+1$ can be factored into $(x + 1)(x^2 + 1)(x^4 + 1)$ by standard polynomial factorization (without even using that the coefficients are elements of GF(2)), which is great because all the factors are sparse and there is nothing sparser. But this just worked because, viewed "backwards", multiplying out the factors did not rely on reduction modulo $x^8$, and that the result is sparse is a coincidence. So for example I want to factor:

• $x^7 + x^5 + x^3 + x + 1$ into $(x + 1)(x^3 + 1)(x^4 + 1)$
• $x^7 + x^6 + x^4 + x^2 + 1$ into $(x^2 + 1)(x^7 + x^4 + 1)$

I could not find an efficient existing algorithm to do so.

So far I have been doing the decomposition in a fairly brute force manner:

# initialize with single-factor
for i in range(256):
    factor[i] = i
    cost[i] = popcnt(i) - 1
# search for improvements
for t in range(4):
    for x in range(1, 256):
        for y in range(1, 256, 2):
            p = clmul(x, y) & 0xff
            if cost[x] + cost[y] < cost[p]:
                cost[p] = cost[x] + cost[y]
                factor[p] = y

But this approach is hopeless for polynomials with a degree of 32 or especially 64. The range of t can actually be smaller, this process converges in very few iterations even for higher degrees - the problem is the inner loops.

Converting it to a circuit-SAT problem (plus binary searching over the number of nonzero coefficients) works well sometimes but other times the SAT solver really struggles with it.

Possibly related to this other question: Minimizing series of XORs

I tried working out some approach based on LLL, but kept running various kinds of trouble due to the modulo $x^{2^k}$. It does not look entirely hopeless yet, but I couldn't make it work.