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 = b0000000000000000000010001011001011101101101010110001011000000000
b0 = 0x000008b2edab1600
b0 = x43 + x39 + x37 + x36 + x33 + x31 + x30 + x29 + x27 + x26 + x24 + x23 + x21 + x19 + x17 + x16 + x12 + x10 + x9

Find r0 = a0 % b0

r0 = b0000000000000000000000100111110000010011001001110100000100111111
r0 = 0x0000027c1327413f
r0 = x41 + x38 + x37 + x36 + x35 + x34 + x28 + x25 + x24 + x21 + x18 + x17 + x16 + x14 + x8 + x5 + x4 + x3 + x2 + x + 1

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

a1 = b0
a1 = b0000000000000000000010001011001011101101101010110001011000000000
a1 = 0x000008b2edab1600
a1 = x43 + x39 + x37 + x36 + x33 + x31 + x30 + x29 + x27 + x26 + x24 + x23 + x21 + x19 + x17 + x16 + x12 + x10 + x9

b1 = r0
b1 = b0000000000000000000000100111110000010011001001110100000100111111
b1 = 0x0000027c1327413f
b1 = x41 + x38 + x37 + x36 + x35 + x34 + x28 + x25 + x24 + x21 + x18 + x17 + x16 + x14 + x8 + x5 + x4 + x3 + x2 + x + 1

Find r1 = a1 % b1

r1 = b0000000000000000000000010100001010100001001101100001001011111100
r1 = 0x00000142a13612fc
r1 = x40 + x38 + x33 + x31 + x29 + x24 + x21 + x20 + x18 + x17 + x12 + x9 + x7 + x6 + x5 + x4 + x3 + x2

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

a2 = b1
a2 = b0000000000000000000000100111110000010011001001110100000100111111
a2 = 0x0000027c1327413f
a2 = x41 + x38 + x37 + x36 + x35 + x34 + x28 + x25 + x24 + x21 + x18 + x17 + x16 + x14 + x8 + x5 + x4 + x3 + x2 + x + 1

b2 = r1
b2 = b0000000000000000000000010100001010100001001101100001001011111100
b2 = 0x00000142a13612fc
b2 = x40 + x38 + x33 + x31 + x29 + x24 + x21 + x20 + x18 + x17 + x12 + x9 + x7 + x6 + x5 + x4 + x3 + x2

Find r2 = a2 % b2

r2 = b0000000000000000000000001111100101010001010010110110010011000111
r2 = 0x000000f9514b64c7
r2 = x39 + x38 + x37 + x36 + x35 + x32 + x30 + x28 + x24 + x22 + x19 + x17 + x16 + x14 + x13 + x10 + x7 + x6 + x2 + x + 1

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

a3 = b2
a3 = b0000000000000000000000010100001010100001001101100001001011111100
a3 = 0x00000142a13612fc
a3 = x40 + x38 + x33 + x31 + x29 + x24 + x21 + x20 + x18 + x17 + x12 + x9 + x7 + x6 + x5 + x4 + x3 + x2

b3 = r2
b3 = b0000000000000000000000001111100101010001010010110110010011000111
b3 = 0x000000f9514b64c7
b3 = x39 + x38 + x37 + x36 + x35 + x32 + x30 + x28 + x24 + x22 + x19 + x17 + x16 + x14 + x13 + x10 + x7 + x6 + x2 + x + 1

Find r3 = a3 % b3

r3 = b0000000000000000000000000100100101010010111010111011111110110101
r3 = 0x0000004952ebbfb5
r3 = x38 + x35 + x32 + x30 + x28 + x25 + x23 + x22 + x21 + x19 + x17 + x16 + x15 + x13 + x12 + x11 + x10 + x9 + x8 + x7 + x5 + x4 + x2 + 1

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

a4 = b3
a4 = b0000000000000000000000001111100101010001010010110110010011000111
a4 = 0x000000f9514b64c7
a4 = x39 + x38 + x37 + x36 + x35 + x32 + x30 + x28 + x24 + x22 + x19 + x17 + x16 + x14 + x13 + x10 + x7 + x6 + x2 + x + 1

b4 = r3
b4 = b0000000000000000000000000100100101010010111010111011111110110101
b4 = 0x0000004952ebbfb5
b4 = x38 + x35 + x32 + x30 + x28 + x25 + x23 + x22 + x21 + x19 + x17 + x16 + x15 + x13 + x12 + x11 + x10 + x9 + x8 + x7 + x5 + x4 + x2 + 1

Find r4 = a4 % b4

r4 = b0000000000000000000000000010001010100110011101111010010000011000
r4 = 0x00000022a677a418
r4 = x37 + x33 + x31 + x29 + x26 + x25 + x22 + x21 + x20 + x18 + x17 + x16 + x15 + x13 + x10 + x4 + x3

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

a5 = b4
a5 = b0000000000000000000000000100100101010010111010111011111110110101
a5 = 0x0000004952ebbfb5
a5 = x38 + x35 + x32 + x30 + x28 + x25 + x23 + x22 + x21 + x19 + x17 + x16 + x15 + x13 + x12 + x11 + x10 + x9 + x8 + x7 + x5 + x4 + x2 + 1

b5 = r4
b5 = b0000000000000000000000000010001010100110011101111010010000011000
b5 = 0x00000022a677a418
b5 = x37 + x33 + x31 + x29 + x26 + x25 + x22 + x21 + x20 + x18 + x17 + x16 + x15 + x13 + x10 + x4 + x3

Find r5 = a5 % b5

r5 = b0000000000000000000000000000110000011110000001001111011110000101
r5 = 0x0000000c1e04f785
r5 = x35 + x34 + x28 + x27 + x26 + x25 + x18 + x15 + x14 + x13 + x12 + x10 + x9 + x8 + x7 + x2 + 1

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

a6 = b5
a6 = b0000000000000000000000000010001010100110011101111010010000011000
a6 = 0x00000022a677a418
a6 = x37 + x33 + x31 + x29 + x26 + x25 + x22 + x21 + x20 + x18 + x17 + x16 + x15 + x13 + x10 + x4 + x3

b6 = r5
b6 = b0000000000000000000000000000110000011110000001001111011110000101
b6 = 0x0000000c1e04f785
b6 = x35 + x34 + x28 + x27 + x26 + x25 + x18 + x15 + x14 + x13 + x12 + x10 + x9 + x8 + x7 + x2 + 1

Find r6 = a6 % b6

r6 = b0000000000000000000000000000011011111100011010010110001010000011
r6 = 0x00000006fc696283
r6 = x34 + x33 + x31 + x30 + x29 + x28 + x27 + x26 + x22 + x21 + x19 + x16 + x14 + x13 + x9 + x7 + x + 1

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

a7 = b6
a7 = b0000000000000000000000000000110000011110000001001111011110000101
a7 = 0x0000000c1e04f785
a7 = x35 + x34 + x28 + x27 + x26 + x25 + x18 + x15 + x14 + x13 + x12 + x10 + x9 + x8 + x7 + x2 + 1

b7 = r6
b7 = b0000000000000000000000000000011011111100011010010110001010000011
b7 = 0x00000006fc696283
b7 = x34 + x33 + x31 + x30 + x29 + x28 + x27 + x26 + x22 + x21 + x19 + x16 + x14 + x13 + x9 + x7 + x + 1

Find r7 = a7 % b7

r7 = b0000000000000000000000000000000111100110110101100011001010000011
r7 = 0x00000001e6d63283
r7 = x32 + x31 + x30 + x29 + x26 + x25 + x23 + x22 + x20 + x18 + x17 + x13 + x12 + x9 + x7 + x + 1

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

a8 = b7
a8 = b0000000000000000000000000000011011111100011010010110001010000011
a8 = 0x00000006fc696283
a8 = x34 + x33 + x31 + x30 + x29 + x28 + x27 + x26 + x22 + x21 + x19 + x16 + x14 + x13 + x9 + x7 + x + 1

b8 = r7
b8 = b0000000000000000000000000000000111100110110101100011001010000011
b8 = 0x00000001e6d63283
b8 = x32 + x31 + x30 + x29 + x26 + x25 + x23 + x22 + x20 + x18 + x17 + x13 + x12 + x9 + x7 + x + 1

Find r8 = a8 % b8

r8 = b0000000000000000000000000000000010000001111001111001101000001100
r8 = 0x0000000081e79a0c
r8 = x31 + x24 + x23 + x22 + x21 + x18 + x17 + x16 + x15 + x12 + x11 + x9 + x3 + x2

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

a9 = b8
a9 = b0000000000000000000000000000000111100110110101100011001010000011
a9 = 0x00000001e6d63283
a9 = x32 + x31 + x30 + x29 + x26 + x25 + x23 + x22 + x20 + x18 + x17 + x13 + x12 + x9 + x7 + x + 1

b9 = r8
b9 = b0000000000000000000000000000000010000001111001111001101000001100
b9 = 0x0000000081e79a0c
b9 = x31 + x24 + x23 + x22 + x21 + x18 + x17 + x16 + x15 + x12 + x11 + x9 + x3 + x2

Find r9 = a9 % b9

r9 = b0000000000000000000000000000000001100100111111101001110010010111
r9 = 0x0000000064fe9c97
r9 = x30 + x29 + x26 + x23 + x22 + x21 + x20 + x19 + x18 + x17 + x15 + x12 + x11 + x10 + x7 + x4 + x2 + x + 1

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

a10 = b9
a10 = b0000000000000000000000000000000010000001111001111001101000001100
a10 = 0x0000000081e79a0c
a10 = x31 + x24 + x23 + x22 + x21 + x18 + x17 + x16 + x15 + x12 + x11 + x9 + x3 + x2

b10 = r9
b10 = b0000000000000000000000000000000001100100111111101001110010010111
b10 = 0x0000000064fe9c97
b10 = x30 + x29 + x26 + x23 + x22 + x21 + x20 + x19 + x18 + x17 + x15 + x12 + x11 + x10 + x7 + x4 + x2 + x + 1

Find r10 = a10 % b10

r10 = b0000000000000000000000000000000000101100111001000011111110110101
r10 = 0x000000002ce43fb5
r10 = x29 + x27 + x26 + x23 + x22 + x21 + x18 + x13 + x12 + x11 + x10 + x9 + x8 + x7 + x5 + x4 + x2 + 1

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

a11 = b10
a11 = b0000000000000000000000000000000001100100111111101001110010010111
a11 = 0x0000000064fe9c97
a11 = x30 + x29 + x26 + x23 + x22 + x21 + x20 + x19 + x18 + x17 + x15 + x12 + x11 + x10 + x7 + x4 + x2 + x + 1

b11 = r10
b11 = b0000000000000000000000000000000000101100111001000011111110110101
b11 = 0x000000002ce43fb5
b11 = x29 + x27 + x26 + x23 + x22 + x21 + x18 + x13 + x12 + x11 + x10 + x9 + x8 + x7 + x5 + x4 + x2 + 1

Find r11 = a11 % b11

r11 = b0000000000000000000000000000000000010001110100101101110001001000
r11 = 0x0000000011d2dc48
r11 = x28 + x24 + x23 + x22 + x20 + x17 + x15 + x14 + x12 + x11 + x10 + x6 + x3

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

a12 = b11
a12 = b0000000000000000000000000000000000101100111001000011111110110101
a12 = 0x000000002ce43fb5
a12 = x29 + x27 + x26 + x23 + x22 + x21 + x18 + x13 + x12 + x11 + x10 + x9 + x8 + x7 + x5 + x4 + x2 + 1

b12 = r11
b12 = b0000000000000000000000000000000000010001110100101101110001001000
b12 = 0x0000000011d2dc48
b12 = x28 + x24 + x23 + x22 + x20 + x17 + x15 + x14 + x12 + x11 + x10 + x6 + x3

Find r12 = a12 % b12

r12 = b0000000000000000000000000000000000001111010000011000011100100101
r12 = 0x000000000f418725
r12 = x27 + x26 + x25 + x24 + x22 + x16 + x15 + x10 + x9 + x8 + x5 + x2 + 1

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

a13 = b12
a13 = b0000000000000000000000000000000000010001110100101101110001001000
a13 = 0x0000000011d2dc48
a13 = x28 + x24 + x23 + x22 + x20 + x17 + x15 + x14 + x12 + x11 + x10 + x6 + x3

b13 = r12
b13 = b0000000000000000000000000000000000001111010000011000011100100101
b13 = 0x000000000f418725
b13 = x27 + x26 + x25 + x24 + x22 + x16 + x15 + x10 + x9 + x8 + x5 + x2 + 1

Find r13 = a13 % b13

r13 = b0000000000000000000000000000000000000000000100000101010100100111
r13 = 0x0000000000105527
r13 = x20 + x14 + x12 + x10 + x8 + x5 + x2 + x + 1

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

a14 = b13
a14 = b0000000000000000000000000000000000001111010000011000011100100101
a14 = 0x000000000f418725
a14 = x27 + x26 + x25 + x24 + x22 + x16 + x15 + x10 + x9 + x8 + x5 + x2 + 1

b14 = r13
b14 = b0000000000000000000000000000000000000000000100000101010100100111
b14 = 0x0000000000105527
b14 = x20 + x14 + x12 + x10 + x8 + x5 + x2 + x + 1

Find r14 = a14 % b14

r14 = b0000000000000000000000000000000000000000000000000000000000000000
r14 = 0x0000000000000000
r14 = 0

r14 is zero, so c=gcd(a,b)=b14

c = b0000000000000000000000000000000000000000000100000101010100100111
c = 0x0000000000105527
c = x20 + x14 + x12 + x10 + x8 + x5 + x2 + x + 1

See also: