gf(2) Berlekamp Algorithm

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

f = b0000000000000000000000000000000000000000000000000000000101110001
f = 0x0000000000000171
f = x8 + x6 + x5 + x4 + 1

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

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 = b00000000000000000000000001110001
v4 = 0x00000071
v4 = x6 + x5 + x4 + 1

v5 = x10 (mod f)
v5 = b00000000000000000000000010110101
v5 = 0x000000b5
v5 = x7 + x5 + x4 + x2 + 1

v6 = x12 (mod f)
v6 = b00000000000000000000000000110110
v6 = 0x00000036
v6 = x5 + x4 + x2 + x

v7 = x14 (mod f)
v7 = b00000000000000000000000011011000
v7 = 0x000000d8
v7 = x7 + x6 + x4 + x3

Represent v0-v7 as matrix Q
Q = 00000001
    00000100
    00010000
    01000000
    01110001
    10110101
    00110110
    11011000
Represent 8x8 identity matrix I
I = 00000001
    00000010
    00000100
    00001000
    00010000
    00100000
    01000000
    10000000
M = Q-I
M = 00000000
    00000110
    00010100
    01001000
    01100001
    10010101
    01110110
    01011000
Find null basis vectors of M

nv0 = b00000000000000000000000000000001
nv0 = 0x00000001
nv0 = 1

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