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 = b0000000000000000001000101010001100101010101101010001000010010010
b0 = 0x000022a32ab51092
b0 = x45 + x41 + x39 + x37 + x33 + x32 + x29 + x27 + x25 + x23 + x21 + x20 + x18 + x16 + x12 + x7 + x4 + x

Find r0 = a0 % b0

r0 = b0000000000000000000110101011000011110001100101001000000011000001
r0 = 0x00001ab0f19480c1
r0 = x44 + x43 + x41 + x39 + x37 + x36 + x31 + x30 + x29 + x28 + x24 + x23 + x20 + x18 + x15 + x7 + x6 + 1

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

a1 = b0
a1 = b0000000000000000001000101010001100101010101101010001000010010010
a1 = 0x000022a32ab51092
a1 = x45 + x41 + x39 + x37 + x33 + x32 + x29 + x27 + x25 + x23 + x21 + x20 + x18 + x16 + x12 + x7 + x4 + x

b1 = r0
b1 = b0000000000000000000110101011000011110001100101001000000011000001
b1 = 0x00001ab0f19480c1
b1 = x44 + x43 + x41 + x39 + x37 + x36 + x31 + x30 + x29 + x28 + x24 + x23 + x20 + x18 + x15 + x7 + x6 + 1

Find r1 = a1 % b1

r1 = b0000000000000000000011010111001000111000000010001001000111010001
r1 = 0x00000d72380891d1
r1 = x43 + x42 + x40 + x38 + x37 + x36 + x33 + x29 + x28 + x27 + x19 + x15 + x12 + x8 + x7 + x6 + x4 + 1

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

a2 = b1
a2 = b0000000000000000000110101011000011110001100101001000000011000001
a2 = 0x00001ab0f19480c1
a2 = x44 + x43 + x41 + x39 + x37 + x36 + x31 + x30 + x29 + x28 + x24 + x23 + x20 + x18 + x15 + x7 + x6 + 1

b2 = r1
b2 = b0000000000000000000011010111001000111000000010001001000111010001
b2 = 0x00000d72380891d1
b2 = x43 + x42 + x40 + x38 + x37 + x36 + x33 + x29 + x28 + x27 + x19 + x15 + x12 + x8 + x7 + x6 + x4 + 1

Find r2 = a2 % b2

r2 = b0000000000000000000000000101010010000001100001011010001101100011
r2 = 0x000000548185a363
r2 = x38 + x36 + x34 + x31 + x24 + x23 + x18 + x16 + x15 + x13 + x9 + x8 + x6 + x5 + x + 1

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

a3 = b2
a3 = b0000000000000000000011010111001000111000000010001001000111010001
a3 = 0x00000d72380891d1
a3 = x43 + x42 + x40 + x38 + x37 + x36 + x33 + x29 + x28 + x27 + x19 + x15 + x12 + x8 + x7 + x6 + x4 + 1

b3 = r2
b3 = b0000000000000000000000000101010010000001100001011010001101100011
b3 = 0x000000548185a363
b3 = x38 + x36 + x34 + x31 + x24 + x23 + x18 + x16 + x15 + x13 + x9 + x8 + x6 + x5 + x + 1

Find r3 = a3 % b3

r3 = b0000000000000000000000000000111000011100110010111101000010011001
r3 = 0x0000000e1ccbd099
r3 = x35 + x34 + x33 + x28 + x27 + x26 + x23 + x22 + x19 + x17 + x16 + x15 + x14 + x12 + x7 + x4 + x3 + 1

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

a4 = b3
a4 = b0000000000000000000000000101010010000001100001011010001101100011
a4 = 0x000000548185a363
a4 = x38 + x36 + x34 + x31 + x24 + x23 + x18 + x16 + x15 + x13 + x9 + x8 + x6 + x5 + x + 1

b4 = r3
b4 = b0000000000000000000000000000111000011100110010111101000010011001
b4 = 0x0000000e1ccbd099
b4 = x35 + x34 + x33 + x28 + x27 + x26 + x23 + x22 + x19 + x17 + x16 + x15 + x14 + x12 + x7 + x4 + x3 + 1

Find r4 = a4 % b4

r4 = b0000000000000000000000000000000000101101011000111100010011111101
r4 = 0x000000002d63c4fd
r4 = x29 + x27 + x26 + x24 + x22 + x21 + x17 + x16 + x15 + x14 + x10 + x7 + x6 + x5 + x4 + x3 + x2 + 1

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

a5 = b4
a5 = b0000000000000000000000000000111000011100110010111101000010011001
a5 = 0x0000000e1ccbd099
a5 = x35 + x34 + x33 + x28 + x27 + x26 + x23 + x22 + x19 + x17 + x16 + x15 + x14 + x12 + x7 + x4 + x3 + 1

b5 = r4
b5 = b0000000000000000000000000000000000101101011000111100010011111101
b5 = 0x000000002d63c4fd
b5 = x29 + x27 + x26 + x24 + x22 + x21 + x17 + x16 + x15 + x14 + x10 + x7 + x6 + x5 + x4 + x3 + x2 + 1

Find r5 = a5 % b5

r5 = b0000000000000000000000000000000000000111000010101110101001110111
r5 = 0x00000000070aea77
r5 = x26 + x25 + x24 + x19 + x17 + x15 + x14 + x13 + x11 + x9 + x6 + x5 + x4 + x2 + x + 1

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

a6 = b5
a6 = b0000000000000000000000000000000000101101011000111100010011111101
a6 = 0x000000002d63c4fd
a6 = x29 + x27 + x26 + x24 + x22 + x21 + x17 + x16 + x15 + x14 + x10 + x7 + x6 + x5 + x4 + x3 + x2 + 1

b6 = r5
b6 = b0000000000000000000000000000000000000111000010101110101001110111
b6 = 0x00000000070aea77
b6 = x26 + x25 + x24 + x19 + x17 + x15 + x14 + x13 + x11 + x9 + x6 + x5 + x4 + x2 + x + 1

Find r6 = a6 % b6

r6 = b0000000000000000000000000000000000000000000000000000000000000000
r6 = 0x0000000000000000
r6 = 0

r6 is zero, so c=gcd(a,b)=b6

c = b0000000000000000000000000000000000000111000010101110101001110111
c = 0x00000000070aea77
c = x26 + x25 + x24 + x19 + x17 + x15 + x14 + x13 + x11 + x9 + x6 + x5 + x4 + x2 + x + 1

See also: