gf(2) Berlekamp Algorithm
If possible, factor polynomial, including at least one irreducible factor.
f = b0000000000000000000000000000000011101011111100101000001100011111
f = 0x00000000ebf2831f
f = x31 + x30 + x29 + x27 + x25 + x24 + x23 + x22 + x21 + x20 + x17 + x15 + x9 + x8 + x4 + x3 + x2 + x + 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 = b0000000000000000000000000000000000111100000101111000010100100001
v16 = 0x000000003c178521
v16 = x29 + x28 + x27 + x26 + x20 + x18 + x17 + x16 + x15 + x10 + x8 + x5 + 1
v17 = x34 (mod f)v17 = b0000000000000000000000000000000000011011101011001001011110011011
v17 = 0x000000001bac979b
v17 = x28 + x27 + x25 + x24 + x23 + x21 + x19 + x18 + x15 + x12 + x10 + x9 + x8 + x7 + x4 + x3 + x + 1
v18 = x36 (mod f)v18 = b0000000000000000000000000000000001101110101100100101111001101100
v18 = 0x000000006eb25e6c
v18 = x30 + x29 + x27 + x26 + x25 + x23 + x21 + x20 + x17 + x14 + x12 + x11 + x10 + x9 + x6 + x5 + x3 + x2
v19 = x38 (mod f)v19 = b0000000000000000000000000000000001101101001011000111111110001110
v19 = 0x000000006d2c7f8e
v19 = x30 + x29 + x27 + x26 + x24 + x21 + x19 + x18 + x14 + x13 + x12 + x11 + x10 + x9 + x8 + x7 + x3 + x2 + x
v20 = x40 (mod f)v20 = b0000000000000000000000000000000001100011010101001111100000000110
v20 = 0x000000006354f806
v20 = x30 + x29 + x25 + x24 + x22 + x20 + x18 + x15 + x14 + x13 + x12 + x11 + x2 + x
v21 = x42 (mod f)v21 = b0000000000000000000000000000000001011010101101101110011000100110
v21 = 0x000000005ab6e626
v21 = x30 + x28 + x27 + x25 + x23 + x21 + x20 + x18 + x17 + x15 + x14 + x13 + x10 + x9 + x5 + x2 + x
v22 = x44 (mod f)v22 = b0000000000000000000000000000000001010110110011000001110110111001
v22 = 0x0000000056cc1db9
v22 = x30 + x28 + x26 + x25 + x23 + x22 + x19 + x18 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x3 + 1
v23 = x46 (mod f)v23 = b0000000000000000000000000000000001100111001001111111001111000101
v23 = 0x000000006727f3c5
v23 = x30 + x29 + x26 + x25 + x24 + x21 + x18 + x17 + x16 + x15 + x14 + x13 + x12 + x9 + x8 + x7 + x6 + x2 + 1
v24 = x48 (mod f)v24 = b0000000000000000000000000000000001001011011110101100100100101010
v24 = 0x000000004b7ac92a
v24 = x30 + x27 + x25 + x24 + x22 + x21 + x20 + x19 + x17 + x15 + x14 + x11 + x8 + x5 + x3 + x
v25 = x50 (mod f)v25 = b0000000000000000000000000000000000010001111111001010000110001001
v25 = 0x0000000011fca189
v25 = x28 + x24 + x23 + x22 + x21 + x20 + x19 + x18 + x15 + x13 + x8 + x7 + x3 + 1
v26 = x52 (mod f)v26 = b0000000000000000000000000000000001000111111100101000011000100100
v26 = 0x0000000047f28624
v26 = x30 + x26 + x25 + x24 + x23 + x22 + x21 + x20 + x17 + x15 + x10 + x9 + x5 + x2
v27 = x54 (mod f)v27 = b0000000000000000000000000000000000100011110111011001110110110001
v27 = 0x0000000023dd9db1
v27 = x29 + x25 + x24 + x23 + x22 + x20 + x19 + x18 + x16 + x15 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + 1
v28 = x56 (mod f)v28 = b0000000000000000000000000000000001100100100001001111010111011011
v28 = 0x000000006484f5db
v28 = x30 + x29 + x26 + x23 + x18 + x15 + x14 + x13 + x12 + x10 + x8 + x7 + x6 + x4 + x3 + x + 1
v29 = x58 (mod f)v29 = b0000000000000000000000000000000001000101111101101101000101010010
v29 = 0x0000000045f6d152
v29 = x30 + x26 + x24 + x23 + x22 + x21 + x20 + x18 + x17 + x15 + x14 + x12 + x8 + x6 + x4 + x
v30 = x60 (mod f)v30 = b0000000000000000000000000000000000101011110011001100000001101001
v30 = 0x000000002bccc069
v30 = x29 + x27 + x25 + x24 + x23 + x22 + x19 + x18 + x15 + x14 + x6 + x5 + x3 + 1
Represent v0-v30 as matrix Q
Q = 0000000000000000000000000000001
0000000000000000000000000000100
0000000000000000000000000010000
0000000000000000000000001000000
0000000000000000000000100000000
0000000000000000000010000000000
0000000000000000001000000000000
0000000000000000100000000000000
0000000000000010000000000000000
0000000000001000000000000000000
0000000000100000000000000000000
0000000010000000000000000000000
0000001000000000000000000000000
0000100000000000000000000000000
0010000000000000000000000000000
1000000000000000000000000000000
0111100000101111000010100100001
0011011101011001001011110011011
1101110101100100101111001101100
1101101001011000111111110001110
1100011010101001111100000000110
1011010101101101110011000100110
1010110110011000001110110111001
1100111001001111111001111000101
1001011011110101100100100101010
0010001111111001010000110001001
1000111111100101000011000100100
0100011110111011001110110110001
1100100100001001111010111011011
1000101111101101101000101010010
0101011110011001100000001101001
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
0111100000101101000010100100001
0011011101011101001011110011011
1101110101101100101111001101100
1101101001001000111111110001110
1100011010001001111100000000110
1011010100101101110011000100110
1010110100011000001110110111001
1100111101001111111001111000101
1001010011110101100100100101010
0010011111111001010000110001001
1000011111100101000011000100100
0101011110111011001110110110001
1110100100001001111010111011011
1100101111101101101000101010010
1101011110011001100000001101001
Find null basis vectors of M
nv0 = b0000000000000000000000000000000000000000000000000000000000000001
nv0 = 0x0000000000000001
nv0 = 1
Only null basis is trivial 1, so f is irreducible.
See also: