gf(2) Berlekamp Algorithm
If possible, factor polynomial, including at least one irreducible factor.
f = b0000000000000000000000000000000010110000110000010101001011111001
f = 0x00000000b0c152f9
f = x31 + x29 + x28 + x23 + x22 + x16 + x14 + x12 + x9 + x7 + x6 + x5 + x4 + x3 + 1
Calculate vn = x2n (mod f) for n=0 to 31
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 = b0000000000000000000000000000000000000000010000000000000000000000
v11 = 0x0000000000400000
v11 = x22
v12 = x24 (mod f)v12 = b0000000000000000000000000000000000000001000000000000000000000000
v12 = 0x0000000001000000
v12 = x24
v13 = x26 (mod f)v13 = b0000000000000000000000000000000000000100000000000000000000000000
v13 = 0x0000000004000000
v13 = x26
v14 = x28 (mod f)v14 = b0000000000000000000000000000000000010000000000000000000000000000
v14 = 0x0000000010000000
v14 = x28
v15 = x30 (mod f)v15 = b0000000000000000000000000000000001000000000000000000000000000000
v15 = 0x0000000040000000
v15 = x30
v16 = x32 (mod f)v16 = b0000000000000000000000000000000001100001100000101010010111110010
v16 = 0x000000006182a5f2
v16 = x30 + x29 + x24 + x23 + x17 + x15 + x13 + x10 + x8 + x7 + x6 + x5 + x4 + x
v17 = x34 (mod f)v17 = b0000000000000000000000000000000001010111010010010110000011000011
v17 = 0x00000000574960c3
v17 = x30 + x28 + x26 + x25 + x24 + x22 + x19 + x16 + x14 + x13 + x7 + x6 + x + 1
v18 = x36 (mod f)v18 = b0000000000000000000000000000000000111100101001110010011011111110
v18 = 0x000000003ca726fe
v18 = x29 + x28 + x27 + x26 + x23 + x21 + x18 + x17 + x16 + x13 + x10 + x9 + x7 + x6 + x5 + x4 + x3 + x2 + x
v19 = x38 (mod f)v19 = b0000000000000000000000000000000001000010010111011100100100000001
v19 = 0x00000000425dc901
v19 = x30 + x25 + x22 + x20 + x19 + x18 + x16 + x15 + x14 + x11 + x8 + 1
v20 = x40 (mod f)v20 = b0000000000000000000000000000000001101000111101011000000111110110
v20 = 0x0000000068f581f6
v20 = x30 + x29 + x27 + x23 + x22 + x21 + x20 + x18 + x16 + x15 + x8 + x7 + x6 + x5 + x4 + x2 + x
v21 = x42 (mod f)v21 = b0000000000000000000000000000000001110010100101011111000011010011
v21 = 0x000000007295f0d3
v21 = x30 + x29 + x28 + x25 + x23 + x20 + x18 + x16 + x15 + x14 + x13 + x12 + x7 + x6 + x4 + x + 1
v22 = x44 (mod f)v22 = b0000000000000000000000000000000000011011000101000011010001000111
v22 = 0x000000001b143447
v22 = x28 + x27 + x25 + x24 + x20 + x18 + x13 + x12 + x10 + x6 + x2 + x + 1
v23 = x46 (mod f)v23 = b0000000000000000000000000000000001101100010100001101000100011100
v23 = 0x000000006c50d11c
v23 = x30 + x29 + x27 + x26 + x22 + x20 + x15 + x14 + x12 + x8 + x4 + x3 + x2
v24 = x48 (mod f)v24 = b0000000000000000000000000000000001100000000000001011001101111011
v24 = 0x000000006000b37b
v24 = x30 + x29 + x15 + x13 + x12 + x9 + x8 + x6 + x5 + x4 + x3 + x + 1
v25 = x50 (mod f)v25 = b0000000000000000000000000000000001010001010000010011101011100111
v25 = 0x0000000051413ae7
v25 = x30 + x28 + x24 + x22 + x16 + x13 + x12 + x11 + x9 + x7 + x6 + x5 + x2 + x + 1
v26 = x52 (mod f)v26 = b0000000000000000000000000000000000100100100001100100111001101110
v26 = 0x0000000024864e6e
v26 = x29 + x26 + x23 + x18 + x17 + x14 + x11 + x10 + x9 + x6 + x5 + x3 + x2 + x
v27 = x54 (mod f)v27 = b0000000000000000000000000000000000100010110110000110101101000001
v27 = 0x0000000022d86b41
v27 = x29 + x25 + x23 + x22 + x20 + x19 + x14 + x13 + x11 + x9 + x8 + x6 + 1
v28 = x56 (mod f)v28 = b0000000000000000000000000000000000111011101000001111111111111101
v28 = 0x000000003ba0fffd
v28 = x29 + x28 + x27 + x25 + x24 + x23 + x21 + x15 + x14 + x13 + x12 + x11 + x10 + x9 + x8 + x7 + x6 + x5 + x4 + x3 + x2 + 1
v29 = x58 (mod f)v29 = b0000000000000000000000000000000001011110010000101010110100001101
v29 = 0x000000005e42ad0d
v29 = x30 + x28 + x27 + x26 + x25 + x22 + x17 + x15 + x13 + x11 + x10 + x8 + x3 + x2 + 1
v30 = x60 (mod f)v30 = b0000000000000000000000000000000000011000100010000001000111000110
v30 = 0x00000000188811c6
v30 = x28 + x27 + x23 + x19 + x12 + x8 + x7 + x6 + x2 + x
Represent v0-v30 as matrix Q
Q = 0000000000000000000000000000001
0000000000000000000000000000100
0000000000000000000000000010000
0000000000000000000000001000000
0000000000000000000000100000000
0000000000000000000010000000000
0000000000000000001000000000000
0000000000000000100000000000000
0000000000000010000000000000000
0000000000001000000000000000000
0000000000100000000000000000000
0000000010000000000000000000000
0000001000000000000000000000000
0000100000000000000000000000000
0010000000000000000000000000000
1000000000000000000000000000000
1100001100000101010010111110010
1010111010010010110000011000011
0111100101001110010011011111110
1000010010111011100100100000001
1101000111101011000000111110110
1110010100101011111000011010011
0011011000101000011010001000111
1101100010100001101000100011100
1100000000000001011001101111011
1010001010000010011101011100111
0100100100001100100111001101110
0100010110110000110101101000001
0111011101000001111111111111101
1011110010000101010110100001101
0011000100010000001000111000110
Represent 31x31 identity matrix I
I = 0000000000000000000000000000001
0000000000000000000000000000010
0000000000000000000000000000100
0000000000000000000000000001000
0000000000000000000000000010000
0000000000000000000000000100000
0000000000000000000000001000000
0000000000000000000000010000000
0000000000000000000000100000000
0000000000000000000001000000000
0000000000000000000010000000000
0000000000000000000100000000000
0000000000000000001000000000000
0000000000000000010000000000000
0000000000000000100000000000000
0000000000000001000000000000000
0000000000000010000000000000000
0000000000000100000000000000000
0000000000001000000000000000000
0000000000010000000000000000000
0000000000100000000000000000000
0000000001000000000000000000000
0000000010000000000000000000000
0000000100000000000000000000000
0000001000000000000000000000000
0000010000000000000000000000000
0000100000000000000000000000000
0001000000000000000000000000000
0010000000000000000000000000000
0100000000000000000000000000000
1000000000000000000000000000000
M = Q-I
M = 0000000000000000000000000000000
0000000000000000000000000000110
0000000000000000000000000010100
0000000000000000000000001001000
0000000000000000000000100010000
0000000000000000000010000100000
0000000000000000001000001000000
0000000000000000100000010000000
0000000000000010000000100000000
0000000000001000000001000000000
0000000000100000000010000000000
0000000010000000000100000000000
0000001000000000001000000000000
0000100000000000010000000000000
0010000000000000100000000000000
1000000000000001000000000000000
1100001100000111010010111110010
1010111010010110110000011000011
0111100101000110010011011111110
1000010010101011100100100000001
1101000111001011000000111110110
1110010101101011111000011010011
0011011010101000011010001000111
1101100110100001101000100011100
1100001000000001011001101111011
1010011010000010011101011100111
0100000100001100100111001101110
0101010110110000110101101000001
0101011101000001111111111111101
1111110010000101010110100001101
1011000100010000001000111000110
Find null basis vectors of M
nv0 = b0000000000000000000000000000000000000000000000000000000000000001
nv0 = 0x0000000000000001
nv0 = 1
Only null basis is trivial 1, so f is irreducible.
See also: