gf(2) Berlekamp Algorithm

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

f = b0000000000000000000000000000000000000000000000000000000000110111 f = 0x0000000000000037 f = x⁵ + x⁴ + x² + x + 1

Calculate v_n = x²ⁿ (mod f) for n=0 to 5

v₀ = x⁰ (mod f)
v₀ = b00000000000000000000000000000001 v₀ = 0x00000001 v₀ = 1
v₁ = x² (mod f)
v₁ = b00000000000000000000000000000100 v₁ = 0x00000004 v₁ = x²
v₂ = x⁴ (mod f)
v₂ = b00000000000000000000000000010000 v₂ = 0x00000010 v₂ = x⁴
v₃ = x⁶ (mod f)
v₃ = b00000000000000000000000000011001 v₃ = 0x00000019 v₃ = x⁴ + x³ + 1
v₄ = x⁸ (mod f)
v₄ = b00000000000000000000000000001010 v₄ = 0x0000000a v₄ = x³ + x

Represent v₀-v₄ as matrix Q
Q = 00001 00100 10000 11001 01010Represent 5x5 identity matrix I
I = 00001 00010 00100 01000 10000M = Q-I
M = 00000 00110 10100 10001 11010Find null basis vectors of M

nv₀ = b00000000000000000000000000000001 nv₀ = 0x00000001 nv₀ = 1

Only null basis is trivial 1, so f is irreducible.