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.
 A: 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.

