gf(2) Berlekamp Algorithm

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

f = b0000000000000000000000000000000000000000000000000000000000000011 f = 0x0000000000000003 f = x + 1

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

v₀ = x⁰ (mod f)
v₀ = b00000000000000000000000000000001 v₀ = 0x00000001 v₀ = 1

Represent v₀-v₀ as matrix Q
Q = 1Represent 1x1 identity matrix I
I = 1M = Q-I
M = 0Find null basis vectors of M

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

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