Loading [MathJax]/jax/output/HTML-CSS/jax.js

Wednesday, August 14, 2013

Berlekamp's Algorithm and Sage

We want to factor f(x)=x8+x6+x4+x3+1 over F2 using Berlekamp's algorithm. You can check up on the algorithm here: http://www.johnkerl.org/doc/iw2009/berlekamp.pdf It is easy to see that f(x)=x2 does not divide f(x), 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 1 when it is run. Next we compute xiq (mod f(x)) for q=2,0<=i<=7. By using the Euclidean algorithm we get: x01 x2x2 x4x4 x6x6 x81+x3+x4+x6 x101+x2+x4+x5+x6+x7 x12x2+x4+x5+x6+x7 x141+x+x3+x4+x5 This gives us the matrix (now using sage again):
   
   
 [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 can 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 g1(x)=1 and g2(x)=x+x2+x5+x6+x7. Again using Euclidean algorithm we get gcd(f(x),g2(x))=x6+x5+x4+x+1 and gcd(f(x),g2(x)1)=x2+x+1. Then, over F2, the canonical factorization is: f(x)=(x6+x5+x4+x+1)(x2+x+1)

No comments:

Post a Comment

Linguistics and Information Theory