gf(2) Berlekamp Algorithm

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

f = b0000000000000000000000000000000000000000000000000000000001100111
f = 0x0000000000000067
f = x6 + x5 + x2 + x + 1

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

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 = b00000000000000000000000000100111
v3 = 0x00000027
v3 = x5 + x2 + x + 1

v4 = x8 (mod f)
v4 = b00000000000000000000000000110101
v4 = 0x00000035
v4 = x5 + x4 + x2 + 1

v5 = x10 (mod f)
v5 = b00000000000000000000000000011010
v5 = 0x0000001a
v5 = x4 + x3 + x

Represent v0-v5 as matrix Q
Q = 000001
    000100
    010000
    100111
    110101
    011010
Represent 6x6 identity matrix I
I = 000001
    000010
    000100
    001000
    010000
    100000
M = Q-I
M = 000000
    000110
    010100
    101111
    100101
    111010
Find null basis vectors of M

nv0 = b00000000000000000000000000000001
nv0 = 0x00000001
nv0 = 1

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