gf(2) Berlekamp Algorithm

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

f = b0000000000000000000000000000000000000000000000000000000000101111 f = 0x000000000000002f 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₃ = b00000000000000000000000000011110 v₃ = 0x0000001e v₃ = x⁴ + x³ + x² + x
v₄ = x⁸ (mod f)
v₄ = b00000000000000000000000000001001 v₄ = 0x00000009 v₄ = x³ + 1

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

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

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