gf(2) Square-free factorization (sff)

Find and remove all squared factors from f.

f = b0000110010101110101000111111010001111111111000000000000000110011
f = 0x0caea3f47fe00033
f = x59 + x58 + x55 + x53 + x51 + x50 + x49 + x47 + x45 + x41 + x40 + x39 + x38 + x37 + x36 + x34 + x30 + x29 + x28 + x27 + x26 + x25 + x24 + x23 + x22 + x21 + x5 + x4 + x + 1

Find the derivative of f (f')

f' = b0000010001010101010100010101000000010101010100000000000000010001
f' = 0x0455515015500011
f' = x58 + x54 + x52 + x50 + x48 + x46 + x44 + x40 + x38 + x36 + x28 + x26 + x24 + x22 + x20 + x4 + 1

Since f' does not equal zero, find g=gcd(f,f')

g = b0000000000000000000000000000000000000000000000000001010000010101
g = 0x0000000000001415
g = x12 + x10 + x4 + x2 + 1

Since g does not equal one, g is a factor of f.

f = gh
h = f/g

Find h=f/g

h = b0000000000000000111101111101100100100100100111111111001100111111
h = 0x0000f7d9249ff33f
h = x47 + x46 + x45 + x44 + x42 + x41 + x40 + x39 + x38 + x36 + x35 + x32 + x29 + x26 + x23 + x20 + x19 + x18 + x17 + x16 + x15 + x14 + x13 + x12 + x9 + x8 + x5 + x4 + x3 + x2 + x + 1

In case either g or h are not square-free...

Find sff(g)
Find sff(h)

Result (f factored into square-free factors)

f = (b0000000000000000000000000000000000000000000000000000000001100111)2(b0000000000000000111101111101100100100100100111111111001100111111)
f = (0x0000000000000067)2(0x0000f7d9249ff33f)
f = (x6 + x5 + x2 + x + 1)2(x47 + x46 + x45 + x44 + x42 + x41 + x40 + x39 + x38 + x36 + x35 + x32 + x29 + x26 + x23 + x20 + x19 + x18 + x17 + x16 + x15 + x14 + x13 + x12 + x9 + x8 + x5 + x4 + x3 + x2 + x + 1)


See also: