gf(2) Calculating the gcd (greatest common divisor)

Euclid's Algorithm

c = gcd(a0,b0)

a0 = b0000000000000000111101111101100100100100100111111111001100111111
a0 = 0x0000f7d9249ff33f
a0 = 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

b0 = b0000000000000000000001111001111000100100100010101110100111101100
b0 = 0x0000079e248ae9ec
b0 = x42 + x41 + x40 + x39 + x36 + x35 + x34 + x33 + x29 + x26 + x23 + x19 + x17 + x15 + x14 + x13 + x11 + x8 + x7 + x6 + x5 + x3 + x2

Find r0 = a0 % b0

r0 = b0000000000000000000000111000001110010001010010000010011101010011
r0 = 0x0000038391482753
r0 = x41 + x40 + x39 + x33 + x32 + x31 + x28 + x24 + x22 + x19 + x13 + x10 + x9 + x8 + x6 + x4 + x + 1

r0 is not zero nor one, so continue...

a1 = b0
a1 = b0000000000000000000001111001111000100100100010101110100111101100
a1 = 0x0000079e248ae9ec
a1 = x42 + x41 + x40 + x39 + x36 + x35 + x34 + x33 + x29 + x26 + x23 + x19 + x17 + x15 + x14 + x13 + x11 + x8 + x7 + x6 + x5 + x3 + x2

b1 = r0
b1 = b0000000000000000000000111000001110010001010010000010011101010011
b1 = 0x0000038391482753
b1 = x41 + x40 + x39 + x33 + x32 + x31 + x28 + x24 + x22 + x19 + x13 + x10 + x9 + x8 + x6 + x4 + x + 1

Find r1 = a1 % b1

r1 = b0000000000000000000000001001100100000110000110101010011101001010
r1 = 0x00000099061aa74a
r1 = x39 + x36 + x35 + x32 + x26 + x25 + x20 + x19 + x17 + x15 + x13 + x10 + x9 + x8 + x6 + x3 + x

r1 is not zero nor one, so continue...

a2 = b1
a2 = b0000000000000000000000111000001110010001010010000010011101010011
a2 = 0x0000038391482753
a2 = x41 + x40 + x39 + x33 + x32 + x31 + x28 + x24 + x22 + x19 + x13 + x10 + x9 + x8 + x6 + x4 + x + 1

b2 = r1
b2 = b0000000000000000000000001001100100000110000110101010011101001010
b2 = 0x00000099061aa74a
b2 = x39 + x36 + x35 + x32 + x26 + x25 + x20 + x19 + x17 + x15 + x13 + x10 + x9 + x8 + x6 + x3 + x

Find r2 = a2 % b2

r2 = b0000000000000000000000000100110010000011000011010101001110100101
r2 = 0x0000004c830d53a5
r2 = x38 + x35 + x34 + x31 + x25 + x24 + x19 + x18 + x16 + x14 + x12 + x9 + x8 + x7 + x5 + x2 + 1

r2 is not zero nor one, so continue...

a3 = b2
a3 = b0000000000000000000000001001100100000110000110101010011101001010
a3 = 0x00000099061aa74a
a3 = x39 + x36 + x35 + x32 + x26 + x25 + x20 + x19 + x17 + x15 + x13 + x10 + x9 + x8 + x6 + x3 + x

b3 = r2
b3 = b0000000000000000000000000100110010000011000011010101001110100101
b3 = 0x0000004c830d53a5
b3 = x38 + x35 + x34 + x31 + x25 + x24 + x19 + x18 + x16 + x14 + x12 + x9 + x8 + x7 + x5 + x2 + 1

Find r3 = a3 % b3

r3 = b0000000000000000000000000000000000000000000000000000000000000000
r3 = 0x0000000000000000
r3 = 0

r3 is zero, so c=gcd(a,b)=b3

c = b0000000000000000000000000100110010000011000011010101001110100101
c = 0x0000004c830d53a5
c = x38 + x35 + x34 + x31 + x25 + x24 + x19 + x18 + x16 + x14 + x12 + x9 + x8 + x7 + x5 + x2 + 1

See also: