gf(2) Berlekamp Algorithm

If possible, factor polynomial, including at least one irreducible factor.

f = b0000000000000000000000000000000000000000000000000000000011000001
f = 0x00000000000000c1
f = x7 + x6 + 1

Calculate vn = x2n (mod f) for n=0 to 7

v0 = x0 (mod f)
v0 = b00000000000000000000000000000001
v0 = 0x00000001
v0 = 1

v1 = x2 (mod f)
v1 = b00000000000000000000000000000100
v1 = 0x00000004
v1 = x2

v2 = x4 (mod f)
v2 = b00000000000000000000000000010000
v2 = 0x00000010
v2 = x4

v3 = x6 (mod f)
v3 = b00000000000000000000000001000000
v3 = 0x00000040
v3 = x6

v4 = x8 (mod f)
v4 = b00000000000000000000000001000011
v4 = 0x00000043
v4 = x6 + x + 1

v5 = x10 (mod f)
v5 = b00000000000000000000000001001111
v5 = 0x0000004f
v5 = x6 + x3 + x2 + x + 1

v6 = x12 (mod f)
v6 = b00000000000000000000000001111111
v6 = 0x0000007f
v6 = x6 + x5 + x4 + x3 + x2 + x + 1

Represent v0-v6 as matrix Q
Q = 0000001
    0000100
    0010000
    1000000
    1000011
    1001111
    1111111
Represent 7x7 identity matrix I
I = 0000001
    0000010
    0000100
    0001000
    0010000
    0100000
    1000000
M = Q-I
M = 0000000
    0000110
    0010100
    1001000
    1010011
    1101111
    0111111
Find null basis vectors of M

nv0 = b00000000000000000000000000000001
nv0 = 0x00000001
nv0 = 1

Only null basis is trivial 1, so f is irreducible.
See also: