Berlekamp's algorithm

My given problem is to factorize the following polynomial, $f(x)=x^8+x^6+x^4+x^3+1$ over $ F_{2}$

Well, my first step was compute $f'(x)=8x^7+6x^5+4x^3+3x^2+1=x^2+1\mod(f)$ Now i find out that $\gcd(f(x),f'(x))=x^6+x^2+x+1=/ 1$, so my question is how to proceed with this, I think I have to made them square-free but I don't know how.

1 Answer

Let us examine how to find the square free part of a polynomial over a finite field, that is, the product of all the roots but taken with multiplicity $1$.

Let $q=p^n$ where $p$ is prime, and let us work over $\mathbb F_q$. We note that, because $\binom{p}{k}=\frac{p!}{k!(p-k)!}$, if $k\neq 0,p$, there will not be any factors of $p$ in the demoninator and so $p\vert \binom{p}{k}$. Because of this $(a+b)^p=a^p+b^p$ when working over any $\mathbb F_p$-algebra, and in particular over $\mathbb F_q[x]$.

Now, because the group of units of a finite field is a cyclic group, and because $p$ does not divide $p^n-1$, the map in $\mathbb F_q^{\times}$ sending $x$ to $x^p$ must be surjective, and so every element of the field has a $p$th root. Combining the above two observation gives us the following result.

Lemma: If $f\in \mathbb F_q[x^p]$, i.e., $f=a_0 + a_p x^p +...a_{kp}x^{kp}$, then $f$ is a perct $p$th power. Explicitpy, $f=g^p$ where $g=\sum a_{ip}^{1/p}x^i$.

For example, in $\mathbb F_2[x]$, we have that $x^8+x^6+x^2=(x^4+x^3+x)^2$.

By repeatedly taking $p$th roots of $f$, we can reduce $f$ to a function with a non-zero derivative.

Lemma: Suppose that $f\in k[x]$ is a polynomia, and that $\alpha$ is a root of $f$ of multiplicity $n$, so that in $\overline{k}[x]$ we can factor $f$ as $(x-\alpha)^ng(x)$ where $g(\alpha)\neq 0$. Then $(x-a)^{n-1}$ divides $f'$.

Proof. Taking derivatives, we have $f'(x)=(x-\alpha)^ng'(x)+n(x-\alpha)^{n-1}g(x)=(x-\alpha)^{n-1}(ng(x)+(x-\alpha)g'(x))$.

Further, if $n$ is not divisible by the characteristic of $k$, we have that other factor of $f'$ does NOT vanish at $\alpha$, and so $f'$ has $\alpha$ as a root of exactly multiplicity $n-1$. However, if $n$ is divisible by the characteristic of $k$, then the other factor does vanish at $\alpha$, and so $\alpha$ must be a root of multiplicity at least $n$.

Let us now return to the case of polynomials over finite fields. Suppose that $f$ is not a perfect $p$th power, so that $f'$ is nonzero. We can now ask what the GCD of $f$ and $f'$ is. Let $\alpha\in \overline{\mathbb F_q}$ be a root of $f$ with multiplicity $n$. Then $\alpha$ will also be a root $(f,f')$ with multiplicity $n$ if $p\vert n$, and with multiplicity $n-1$ otherwise. Therefore we must have that $f/(f,f')$ will have the same roots as $f$ but with multiplicity $1$, except for the roots that had multiplicity a multiple of $p$, which will all be missing.

To summarize:

Let $f=\prod (x-\alpha_i)^{a_i} \prod (x-\beta_j)^{pb_j}$ where $p \nmid a_i$. If the set of $\alpha_i$ is non-empty (so that $f$ isn't a perfect $p$th power, which we have dealt with earlier), $f/(f,f')=\prod (x-\alpha_i)$.

Now, if you can factor $f/(f,f')$ into irreducible factors, you can go back and divide those factors from $(f,f')$ to recover $\prod (x-\beta_j)^{pb_j}$, take the $p$th root, rinse, and repeat.

Therefore, to get something which you can input to Berlekamp's algorithm (which must be square free), you can just take $f/(f,f')$ unless $f'=0$, in which case you need to take the $p$th root of all the monomial terms in $f$ first.