Factoring Polynomials with Berlekamp's Algorithm in Sage

We want to factor over using Berlekamp’s algorithm. You can check up on the algorithm here. It is easy to see that does not divide , but one can check this using the euclidean algorithm. In sage one checks this as follows:

S.<x> = PolynomialRing(GF(2),'x')  
f = x**8 + x**6 + x**4 + x**3 + 1; g = x**2
f.gcd(g)  

which will result in when it is run. Next we compute for . By using the Euclidean algorithm we get:

This gives us the matrix:

[1 0 0 0 0 0 0 0]  
[0 0 1 0 0 0 0 0]  
[0 0 0 0 1 0 0 0]  
[0 0 0 0 0 0 1 0]  
[1 0 0 1 1 0 1 0]  
[1 0 1 1 1 1 0 0]  
[0 0 1 0 1 1 1 1]  
[1 1 0 1 1 1 0 0]  

Then, subtracting the identity matrix we get:

[0 0 0 0 0 0 0 0]  
[0 1 1 0 0 0 0 0]  
[0 0 1 0 1 0 0 0]  
[0 0 0 1 0 0 1 0]  
[1 0 0 1 0 0 1 0]  
[1 0 1 1 1 0 0 0]  
[0 0 1 0 1 1 0 1]  
[1 1 0 1 1 1 0 1]  

We now use sage to find the basis of the null space of the above matrix as follows:

M = MatrixSpace(GF(2), 8, 8)  
A = M([0, 0, 0, 0, 0, 0, 0, 0,   
       0, 1, 1, 0, 0, 0, 0, 0,  
       0, 0, 1, 0, 1, 0, 0, 0,  
       0, 0, 0, 1, 0, 0, 1, 0,  
       1, 0, 0, 1, 0, 0, 1, 0,  
       1, 0, 1, 1, 1, 0, 0, 0,  
       0, 0, 1, 0, 1, 1, 0, 1,  
       1, 1, 0, 1, 1, 1, 0, 1])  
         
A.kernel()

Which will give the following result:

Vector space of degree 8 and dimension 2 over Finite Field of size 2  
Basis matrix:  
[1 0 0 0 0 0 0 0]  
[0 1 1 0 0 1 1 1]  

These correspond to the polynomials and . Again using Euclidean algorithm we get and . Then, over , the canonical factorization is: