gf(2) Berlekamp Algorithm

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

f = b0000000000000000000000000000000000000000001001111000101010011001
f = 0x0000000000278a99
f = x21 + x18 + x17 + x16 + x15 + x11 + x9 + x7 + x4 + x3 + 1

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

v0 = x0 (mod f)
v0 = b0000000000000000000000000000000000000000000000000000000000000001
v0 = 0x0000000000000001
v0 = 1

v1 = x2 (mod f)
v1 = b0000000000000000000000000000000000000000000000000000000000000100
v1 = 0x0000000000000004
v1 = x2

v2 = x4 (mod f)
v2 = b0000000000000000000000000000000000000000000000000000000000010000
v2 = 0x0000000000000010
v2 = x4

v3 = x6 (mod f)
v3 = b0000000000000000000000000000000000000000000000000000000001000000
v3 = 0x0000000000000040
v3 = x6

v4 = x8 (mod f)
v4 = b0000000000000000000000000000000000000000000000000000000100000000
v4 = 0x0000000000000100
v4 = x8

v5 = x10 (mod f)
v5 = b0000000000000000000000000000000000000000000000000000010000000000
v5 = 0x0000000000000400
v5 = x10

v6 = x12 (mod f)
v6 = b0000000000000000000000000000000000000000000000000001000000000000
v6 = 0x0000000000001000
v6 = x12

v7 = x14 (mod f)
v7 = b0000000000000000000000000000000000000000000000000100000000000000
v7 = 0x0000000000004000
v7 = x14

v8 = x16 (mod f)
v8 = b0000000000000000000000000000000000000000000000010000000000000000
v8 = 0x0000000000010000
v8 = x16

v9 = x18 (mod f)
v9 = b0000000000000000000000000000000000000000000001000000000000000000
v9 = 0x0000000000040000
v9 = x18

v10 = x20 (mod f)
v10 = b0000000000000000000000000000000000000000000100000000000000000000
v10 = 0x0000000000100000
v10 = x20

v11 = x22 (mod f)
v11 = b0000000000000000000000000000000000000000000011110001010100110010
v11 = 0x00000000000f1532
v11 = x19 + x18 + x17 + x16 + x12 + x10 + x8 + x5 + x4 + x

v12 = x24 (mod f)
v12 = b0000000000000000000000000000000000000000000110111101111001010001
v12 = 0x00000000001bde51
v12 = x20 + x19 + x17 + x16 + x15 + x14 + x12 + x11 + x10 + x9 + x6 + x4 + 1

v13 = x26 (mod f)
v13 = b0000000000000000000000000000000000000000000001111110011011101111
v13 = 0x000000000007e6ef
v13 = x18 + x17 + x16 + x15 + x14 + x13 + x10 + x9 + x7 + x6 + x5 + x3 + x2 + x + 1

v14 = x28 (mod f)
v14 = b0000000000000000000000000000000000000000000111111001101110111100
v14 = 0x00000000001f9bbc
v14 = x20 + x19 + x18 + x17 + x16 + x15 + x12 + x11 + x9 + x8 + x7 + x5 + x4 + x3 + x2

v15 = x30 (mod f)
v15 = b0000000000000000000000000000000000000000000101101111000101011011
v15 = 0x000000000016f15b
v15 = x20 + x18 + x17 + x15 + x14 + x13 + x12 + x8 + x6 + x4 + x3 + x + 1

v16 = x32 (mod f)
v16 = b0000000000000000000000000000000000000000000101001101000001011110
v16 = 0x000000000014d05e
v16 = x20 + x18 + x15 + x14 + x12 + x6 + x4 + x3 + x2 + x

v17 = x34 (mod f)
v17 = b0000000000000000000000000000000000000000000111000101010001001010
v17 = 0x00000000001c544a
v17 = x20 + x19 + x18 + x14 + x12 + x10 + x6 + x3 + x

v18 = x36 (mod f)
v18 = b0000000000000000000000000000000000000000000110011100111010000011
v18 = 0x000000000019ce83
v18 = x20 + x19 + x16 + x15 + x14 + x11 + x10 + x9 + x7 + x + 1

v19 = x38 (mod f)
v19 = b0000000000000000000000000000000000000000000011111010010110100111
v19 = 0x00000000000fa5a7
v19 = x19 + x18 + x17 + x16 + x15 + x13 + x10 + x8 + x7 + x5 + x2 + x + 1

v20 = x40 (mod f)
v20 = b0000000000000000000000000000000000000000000110010001110000000101
v20 = 0x0000000000191c05
v20 = x20 + x19 + x16 + x12 + x11 + x10 + x2 + 1

Represent v0-v20 as matrix Q
Q = 000000000000000000001
    000000000000000000100
    000000000000000010000
    000000000000001000000
    000000000000100000000
    000000000010000000000
    000000001000000000000
    000000100000000000000
    000010000000000000000
    001000000000000000000
    100000000000000000000
    011110001010100110010
    110111101111001010001
    001111110011011101111
    111111001101110111100
    101101111000101011011
    101001101000001011110
    111000101010001001010
    110011100111010000011
    011111010010110100111
    110010001110000000101
Represent 21x21 identity matrix I
I = 000000000000000000001
    000000000000000000010
    000000000000000000100
    000000000000000001000
    000000000000000010000
    000000000000000100000
    000000000000001000000
    000000000000010000000
    000000000000100000000
    000000000001000000000
    000000000010000000000
    000000000100000000000
    000000001000000000000
    000000010000000000000
    000000100000000000000
    000001000000000000000
    000010000000000000000
    000100000000000000000
    001000000000000000000
    010000000000000000000
    100000000000000000000
M = Q-I
M = 000000000000000000000
    000000000000000000110
    000000000000000010100
    000000000000001001000
    000000000000100010000
    000000000010000100000
    000000001000001000000
    000000100000010000000
    000010000000100000000
    001000000001000000000
    100000000010000000000
    011110001110100110010
    110111100111001010001
    001111100011011101111
    111111101101110111100
    101100111000101011011
    101011101000001011110
    111100101010001001010
    111011100111010000011
    001111010010110100111
    010010001110000000101
Find null basis vectors of M

nv0 = b0000000000000000000000000000000000000000000000000000000000000001
nv0 = 0x0000000000000001
nv0 = 1

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