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

Euclid's Algorithm

c = gcd(a0,b0)

a0 = b0110011001110111111000100000000101000110010100001000111110110111
a0 = 0x6677e20146508fb7
a0 = x62 + x61 + x58 + x57 + x54 + x53 + x52 + x50 + x49 + x48 + x47 + x46 + x45 + x41 + x32 + x30 + x26 + x25 + x22 + x20 + x15 + x11 + x10 + x9 + x8 + x7 + x5 + x4 + x2 + x + 1

b0 = b0001001001110000010000101110001001010001010011001000101011011100
b0 = 0x127042e2514c8adc
b0 = x60 + x57 + x54 + x53 + x52 + x46 + x41 + x39 + x38 + x37 + x33 + x30 + x28 + x24 + x22 + x19 + x18 + x15 + x11 + x9 + x7 + x6 + x4 + x3 + x2

Find r0 = a0 % b0

r0 = b0000101101010110011011000100110010100001111110111011000101111111
r0 = 0x0b566c4ca1fbb17f
r0 = x59 + x57 + x56 + x54 + x52 + x50 + x49 + x46 + x45 + x43 + x42 + x38 + x35 + x34 + x31 + x29 + x24 + x23 + x22 + x21 + x20 + x19 + x17 + x16 + x15 + x13 + x12 + x8 + x6 + x5 + x4 + x3 + x2 + x + 1

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

a1 = b0
a1 = b0001001001110000010000101110001001010001010011001000101011011100
a1 = 0x127042e2514c8adc
a1 = x60 + x57 + x54 + x53 + x52 + x46 + x41 + x39 + x38 + x37 + x33 + x30 + x28 + x24 + x22 + x19 + x18 + x15 + x11 + x9 + x7 + x6 + x4 + x3 + x2

b1 = r0
b1 = b0000101101010110011011000100110010100001111110111011000101111111
b1 = 0x0b566c4ca1fbb17f
b1 = x59 + x57 + x56 + x54 + x52 + x50 + x49 + x46 + x45 + x43 + x42 + x38 + x35 + x34 + x31 + x29 + x24 + x23 + x22 + x21 + x20 + x19 + x17 + x16 + x15 + x13 + x12 + x8 + x6 + x5 + x4 + x3 + x2 + x + 1

Find r1 = a1 % b1

r1 = b0000010011011100100110100111101100010010101110111110100000100010
r1 = 0x04dc9a7b12bbe822
r1 = x58 + x55 + x54 + x52 + x51 + x50 + x47 + x44 + x43 + x41 + x38 + x37 + x36 + x35 + x33 + x32 + x28 + x25 + x23 + x21 + x20 + x19 + x17 + x16 + x15 + x14 + x13 + x11 + x5 + x

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

a2 = b1
a2 = b0000101101010110011011000100110010100001111110111011000101111111
a2 = 0x0b566c4ca1fbb17f
a2 = x59 + x57 + x56 + x54 + x52 + x50 + x49 + x46 + x45 + x43 + x42 + x38 + x35 + x34 + x31 + x29 + x24 + x23 + x22 + x21 + x20 + x19 + x17 + x16 + x15 + x13 + x12 + x8 + x6 + x5 + x4 + x3 + x2 + x + 1

b2 = r1
b2 = b0000010011011100100110100111101100010010101110111110100000100010
b2 = 0x04dc9a7b12bbe822
b2 = x58 + x55 + x54 + x52 + x51 + x50 + x47 + x44 + x43 + x41 + x38 + x37 + x36 + x35 + x33 + x32 + x28 + x25 + x23 + x21 + x20 + x19 + x17 + x16 + x15 + x14 + x13 + x11 + x5 + x

Find r2 = a2 % b2

r2 = b0000001011101111010110001011101010000100100011000110000100111011
r2 = 0x02ef58ba848c613b
r2 = x57 + x55 + x54 + x53 + x51 + x50 + x49 + x48 + x46 + x44 + x43 + x39 + x37 + x36 + x35 + x33 + x31 + x26 + x23 + x19 + x18 + x14 + x13 + x8 + x5 + x4 + x3 + x + 1

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

a3 = b2
a3 = b0000010011011100100110100111101100010010101110111110100000100010
a3 = 0x04dc9a7b12bbe822
a3 = x58 + x55 + x54 + x52 + x51 + x50 + x47 + x44 + x43 + x41 + x38 + x37 + x36 + x35 + x33 + x32 + x28 + x25 + x23 + x21 + x20 + x19 + x17 + x16 + x15 + x14 + x13 + x11 + x5 + x

b3 = r2
b3 = b0000001011101111010110001011101010000100100011000110000100111011
b3 = 0x02ef58ba848c613b
b3 = x57 + x55 + x54 + x53 + x51 + x50 + x49 + x48 + x46 + x44 + x43 + x39 + x37 + x36 + x35 + x33 + x31 + x26 + x23 + x19 + x18 + x14 + x13 + x8 + x5 + x4 + x3 + x + 1

Find r3 = a3 % b3

r3 = b0000000100000010001010110000111000011011101000110010101001010100
r3 = 0x01022b0e1ba32a54
r3 = x56 + x49 + x45 + x43 + x41 + x40 + x35 + x34 + x33 + x28 + x27 + x25 + x24 + x23 + x21 + x17 + x16 + x13 + x11 + x9 + x6 + x4 + x2

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

a4 = b3
a4 = b0000001011101111010110001011101010000100100011000110000100111011
a4 = 0x02ef58ba848c613b
a4 = x57 + x55 + x54 + x53 + x51 + x50 + x49 + x48 + x46 + x44 + x43 + x39 + x37 + x36 + x35 + x33 + x31 + x26 + x23 + x19 + x18 + x14 + x13 + x8 + x5 + x4 + x3 + x + 1

b4 = r3
b4 = b0000000100000010001010110000111000011011101000110010101001010100
b4 = 0x01022b0e1ba32a54
b4 = x56 + x49 + x45 + x43 + x41 + x40 + x35 + x34 + x33 + x28 + x27 + x25 + x24 + x23 + x21 + x17 + x16 + x13 + x11 + x9 + x6 + x4 + x2

Find r4 = a4 % b4

r4 = b0000000011101011000011101010011010110011110010100011010110010011
r4 = 0x00eb0ea6b3ca3593
r4 = x55 + x54 + x53 + x51 + x49 + x48 + x43 + x42 + x41 + x39 + x37 + x34 + x33 + x31 + x29 + x28 + x25 + x24 + x23 + x22 + x19 + x17 + x13 + x12 + x10 + x8 + x7 + x4 + x + 1

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

a5 = b4
a5 = b0000000100000010001010110000111000011011101000110010101001010100
a5 = 0x01022b0e1ba32a54
a5 = x56 + x49 + x45 + x43 + x41 + x40 + x35 + x34 + x33 + x28 + x27 + x25 + x24 + x23 + x21 + x17 + x16 + x13 + x11 + x9 + x6 + x4 + x2

b5 = r4
b5 = b0000000011101011000011101010011010110011110010100011010110010011
b5 = 0x00eb0ea6b3ca3593
b5 = x55 + x54 + x53 + x51 + x49 + x48 + x43 + x42 + x41 + x39 + x37 + x34 + x33 + x31 + x29 + x28 + x25 + x24 + x23 + x22 + x19 + x17 + x13 + x12 + x10 + x8 + x7 + x4 + x + 1

Find r5 = a5 % b5

r5 = b0000000000111111001110001110010111001111111111010111010011100001
r5 = 0x003f38e5cffd74e1
r5 = x53 + x52 + x51 + x50 + x49 + x48 + x45 + x44 + x43 + x39 + x38 + x37 + x34 + x32 + x31 + x30 + x27 + x26 + x25 + x24 + x23 + x22 + x21 + x20 + x19 + x18 + x16 + x14 + x13 + x12 + x10 + x7 + x6 + x5 + 1

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

a6 = b5
a6 = b0000000011101011000011101010011010110011110010100011010110010011
a6 = 0x00eb0ea6b3ca3593
a6 = x55 + x54 + x53 + x51 + x49 + x48 + x43 + x42 + x41 + x39 + x37 + x34 + x33 + x31 + x29 + x28 + x25 + x24 + x23 + x22 + x19 + x17 + x13 + x12 + x10 + x8 + x7 + x4 + x + 1

b6 = r5
b6 = b0000000000111111001110001110010111001111111111010111010011100001
b6 = 0x003f38e5cffd74e1
b6 = x53 + x52 + x51 + x50 + x49 + x48 + x45 + x44 + x43 + x39 + x38 + x37 + x34 + x32 + x31 + x30 + x27 + x26 + x25 + x24 + x23 + x22 + x21 + x20 + x19 + x18 + x16 + x14 + x13 + x12 + x10 + x7 + x6 + x5 + 1

Find r6 = a6 % b6

r6 = b0000000000010111111011010011000110001100001111111110011000010111
r6 = 0x0017ed318c3fe617
r6 = x52 + x50 + x49 + x48 + x47 + x46 + x45 + x43 + x42 + x40 + x37 + x36 + x32 + x31 + x27 + x26 + x21 + x20 + x19 + x18 + x17 + x16 + x15 + x14 + x13 + x10 + x9 + x4 + x2 + x + 1

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

a7 = b6
a7 = b0000000000111111001110001110010111001111111111010111010011100001
a7 = 0x003f38e5cffd74e1
a7 = x53 + x52 + x51 + x50 + x49 + x48 + x45 + x44 + x43 + x39 + x38 + x37 + x34 + x32 + x31 + x30 + x27 + x26 + x25 + x24 + x23 + x22 + x21 + x20 + x19 + x18 + x16 + x14 + x13 + x12 + x10 + x7 + x6 + x5 + 1

b7 = r6
b7 = b0000000000010111111011010011000110001100001111111110011000010111
b7 = 0x0017ed318c3fe617
b7 = x52 + x50 + x49 + x48 + x47 + x46 + x45 + x43 + x42 + x40 + x37 + x36 + x32 + x31 + x27 + x26 + x21 + x20 + x19 + x18 + x17 + x16 + x15 + x14 + x13 + x10 + x9 + x4 + x2 + x + 1

Find r7 = a7 % b7

r7 = b0000000000000111000011111011011101011011101111010101111011011000
r7 = 0x00070fb75bbd5ed8
r7 = x50 + x49 + x48 + x43 + x42 + x41 + x40 + x39 + x37 + x36 + x34 + x33 + x32 + x30 + x28 + x27 + x25 + x24 + x23 + x21 + x20 + x19 + x18 + x16 + x14 + x12 + x11 + x10 + x9 + x7 + x6 + x4 + x3

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

a8 = b7
a8 = b0000000000010111111011010011000110001100001111111110011000010111
a8 = 0x0017ed318c3fe617
a8 = x52 + x50 + x49 + x48 + x47 + x46 + x45 + x43 + x42 + x40 + x37 + x36 + x32 + x31 + x27 + x26 + x21 + x20 + x19 + x18 + x17 + x16 + x15 + x14 + x13 + x10 + x9 + x4 + x2 + x + 1

b8 = r7
b8 = b0000000000000111000011111011011101011011101111010101111011011000
b8 = 0x00070fb75bbd5ed8
b8 = x50 + x49 + x48 + x43 + x42 + x41 + x40 + x39 + x37 + x36 + x34 + x33 + x32 + x30 + x28 + x27 + x25 + x24 + x23 + x21 + x20 + x19 + x18 + x16 + x14 + x12 + x11 + x10 + x9 + x7 + x6 + x4 + x3

Find r8 = a8 % b8

r8 = b0000000000000010110000110011010100001110000011010111111000011111
r8 = 0x0002c3350e0d7e1f
r8 = x49 + x47 + x46 + x41 + x40 + x37 + x36 + x34 + x32 + x27 + x26 + x25 + x19 + x18 + x16 + x14 + x13 + x12 + x11 + x10 + x9 + x4 + x3 + x2 + x + 1

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

a9 = b8
a9 = b0000000000000111000011111011011101011011101111010101111011011000
a9 = 0x00070fb75bbd5ed8
a9 = x50 + x49 + x48 + x43 + x42 + x41 + x40 + x39 + x37 + x36 + x34 + x33 + x32 + x30 + x28 + x27 + x25 + x24 + x23 + x21 + x20 + x19 + x18 + x16 + x14 + x12 + x11 + x10 + x9 + x7 + x6 + x4 + x3

b9 = r8
b9 = b0000000000000010110000110011010100001110000011010111111000011111
b9 = 0x0002c3350e0d7e1f
b9 = x49 + x47 + x46 + x41 + x40 + x37 + x36 + x34 + x32 + x27 + x26 + x25 + x19 + x18 + x16 + x14 + x13 + x12 + x11 + x10 + x9 + x4 + x3 + x2 + x + 1

Find r9 = a9 % b9

r9 = b0000000000000000010010101110100001001001101010101101110011111001
r9 = 0x00004ae849aadcf9
r9 = x46 + x43 + x41 + x39 + x38 + x37 + x35 + x30 + x27 + x24 + x23 + x21 + x19 + x17 + x15 + x14 + x12 + x11 + x10 + x7 + x6 + x5 + x4 + x3 + 1

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

a10 = b9
a10 = b0000000000000010110000110011010100001110000011010111111000011111
a10 = 0x0002c3350e0d7e1f
a10 = x49 + x47 + x46 + x41 + x40 + x37 + x36 + x34 + x32 + x27 + x26 + x25 + x19 + x18 + x16 + x14 + x13 + x12 + x11 + x10 + x9 + x4 + x3 + x2 + x + 1

b10 = r9
b10 = b0000000000000000010010101110100001001001101010101101110011111001
b10 = 0x00004ae849aadcf9
b10 = x46 + x43 + x41 + x39 + x38 + x37 + x35 + x30 + x27 + x24 + x23 + x21 + x19 + x17 + x15 + x14 + x12 + x11 + x10 + x7 + x6 + x5 + x4 + x3 + 1

Find r10 = a10 % b10

r10 = b0000000000000000000000011010011111010000000011100010000000100101
r10 = 0x000001a7d00e2025
r10 = x40 + x39 + x37 + x34 + x33 + x32 + x31 + x30 + x28 + x19 + x18 + x17 + x13 + x5 + x2 + 1

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

a11 = b10
a11 = b0000000000000000010010101110100001001001101010101101110011111001
a11 = 0x00004ae849aadcf9
a11 = x46 + x43 + x41 + x39 + x38 + x37 + x35 + x30 + x27 + x24 + x23 + x21 + x19 + x17 + x15 + x14 + x12 + x11 + x10 + x7 + x6 + x5 + x4 + x3 + 1

b11 = r10
b11 = b0000000000000000000000011010011111010000000011100010000000100101
b11 = 0x000001a7d00e2025
b11 = x40 + x39 + x37 + x34 + x33 + x32 + x31 + x30 + x28 + x19 + x18 + x17 + x13 + x5 + x2 + 1

Find r11 = a11 % b11

r11 = b0000000000000000000000001010010111001011011101011101001001100001
r11 = 0x000000a5cb75d261
r11 = x39 + x37 + x34 + x32 + x31 + x30 + x27 + x25 + x24 + x22 + x21 + x20 + x18 + x16 + x15 + x14 + x12 + x9 + x6 + x5 + 1

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

a12 = b11
a12 = b0000000000000000000000011010011111010000000011100010000000100101
a12 = 0x000001a7d00e2025
a12 = x40 + x39 + x37 + x34 + x33 + x32 + x31 + x30 + x28 + x19 + x18 + x17 + x13 + x5 + x2 + 1

b12 = r11
b12 = b0000000000000000000000001010010111001011011101011101001001100001
b12 = 0x000000a5cb75d261
b12 = x39 + x37 + x34 + x32 + x31 + x30 + x27 + x25 + x24 + x22 + x21 + x20 + x18 + x16 + x15 + x14 + x12 + x9 + x6 + x5 + 1

Find r12 = a12 % b12

r12 = b0000000000000000000000000100100110001101100100000101011010000110
r12 = 0x000000498d905686
r12 = x38 + x35 + x32 + x31 + x27 + x26 + x24 + x23 + x20 + x14 + x12 + x10 + x9 + x7 + x2 + x

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

a13 = b12
a13 = b0000000000000000000000001010010111001011011101011101001001100001
a13 = 0x000000a5cb75d261
a13 = x39 + x37 + x34 + x32 + x31 + x30 + x27 + x25 + x24 + x22 + x21 + x20 + x18 + x16 + x15 + x14 + x12 + x9 + x6 + x5 + 1

b13 = r12
b13 = b0000000000000000000000000100100110001101100100000101011010000110
b13 = 0x000000498d905686
b13 = x38 + x35 + x32 + x31 + x27 + x26 + x24 + x23 + x20 + x14 + x12 + x10 + x9 + x7 + x2 + x

Find r13 = a13 % b13

r13 = b0000000000000000000000000011011011010000010101010111111101101101
r13 = 0x00000036d0557f6d
r13 = x37 + x36 + x34 + x33 + x31 + x30 + x28 + x22 + x20 + x18 + x16 + x14 + x13 + x12 + x11 + x10 + x9 + x8 + x6 + x5 + x3 + x2 + 1

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

a14 = b13
a14 = b0000000000000000000000000100100110001101100100000101011010000110
a14 = 0x000000498d905686
a14 = x38 + x35 + x32 + x31 + x27 + x26 + x24 + x23 + x20 + x14 + x12 + x10 + x9 + x7 + x2 + x

b14 = r13
b14 = b0000000000000000000000000011011011010000010101010111111101101101
b14 = 0x00000036d0557f6d
b14 = x37 + x36 + x34 + x33 + x31 + x30 + x28 + x22 + x20 + x18 + x16 + x14 + x13 + x12 + x11 + x10 + x9 + x8 + x6 + x5 + x3 + x2 + 1

Find r14 = a14 % b14

r14 = b0000000000000000000000000001001011111101011011111101011100110001
r14 = 0x00000012fd6fd731
r14 = x36 + x33 + x31 + x30 + x29 + x28 + x27 + x26 + x24 + x22 + x21 + x19 + x18 + x17 + x16 + x15 + x14 + x12 + x10 + x9 + x8 + x5 + x4 + 1

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

a15 = b14
a15 = b0000000000000000000000000011011011010000010101010111111101101101
a15 = 0x00000036d0557f6d
a15 = x37 + x36 + x34 + x33 + x31 + x30 + x28 + x22 + x20 + x18 + x16 + x14 + x13 + x12 + x11 + x10 + x9 + x8 + x6 + x5 + x3 + x2 + 1

b15 = r14
b15 = b0000000000000000000000000001001011111101011011111101011100110001
b15 = 0x00000012fd6fd731
b15 = x36 + x33 + x31 + x30 + x29 + x28 + x27 + x26 + x24 + x22 + x21 + x19 + x18 + x17 + x16 + x15 + x14 + x12 + x10 + x9 + x8 + x5 + x4 + 1

Find r15 = a15 % b15

r15 = b0000000000000000000000000000000111010111111001010000011000111110
r15 = 0x00000001d7e5063e
r15 = x32 + x31 + x30 + x28 + x26 + x25 + x24 + x23 + x22 + x21 + x18 + x16 + x10 + x9 + x5 + x4 + x3 + x2 + x

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

a16 = b15
a16 = b0000000000000000000000000001001011111101011011111101011100110001
a16 = 0x00000012fd6fd731
a16 = x36 + x33 + x31 + x30 + x29 + x28 + x27 + x26 + x24 + x22 + x21 + x19 + x18 + x17 + x16 + x15 + x14 + x12 + x10 + x9 + x8 + x5 + x4 + 1

b16 = r15
b16 = b0000000000000000000000000000000111010111111001010000011000111110
b16 = 0x00000001d7e5063e
b16 = x32 + x31 + x30 + x28 + x26 + x25 + x24 + x23 + x22 + x21 + x18 + x16 + x10 + x9 + x5 + x4 + x3 + x2 + x

Find r16 = a16 % b16

r16 = b0000000000000000000000000000000011101011111100101000001100011111
r16 = 0x00000000ebf2831f
r16 = x31 + x30 + x29 + x27 + x25 + x24 + x23 + x22 + x21 + x20 + x17 + x15 + x9 + x8 + x4 + x3 + x2 + x + 1

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

a17 = b16
a17 = b0000000000000000000000000000000111010111111001010000011000111110
a17 = 0x00000001d7e5063e
a17 = x32 + x31 + x30 + x28 + x26 + x25 + x24 + x23 + x22 + x21 + x18 + x16 + x10 + x9 + x5 + x4 + x3 + x2 + x

b17 = r16
b17 = b0000000000000000000000000000000011101011111100101000001100011111
b17 = 0x00000000ebf2831f
b17 = x31 + x30 + x29 + x27 + x25 + x24 + x23 + x22 + x21 + x20 + x17 + x15 + x9 + x8 + x4 + x3 + x2 + x + 1

Find r17 = a17 % b17

r17 = b0000000000000000000000000000000000000000000000000000000000000000
r17 = 0x0000000000000000
r17 = 0

r17 is zero, so c=gcd(a,b)=b17

c = b0000000000000000000000000000000011101011111100101000001100011111
c = 0x00000000ebf2831f
c = x31 + x30 + x29 + x27 + x25 + x24 + x23 + x22 + x21 + x20 + x17 + x15 + x9 + x8 + x4 + x3 + x2 + x + 1

See also: