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:
x0≡1
x2≡x2
x4≡x4
x6≡x6
x8≡1+x3+x4+x6
x10≡1+x2+x4+x5+x6+x7
x12≡x2+x4+x5+x6+x7
x14≡1+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