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 = b0000000000000000010000110000110000001110100101100010101100011000
b0 = 0x0000430c0e962b18
b0 = x46 + x41 + x40 + x35 + x34 + x27 + x26 + x25 + x23 + x20 + x18 + x17 + x13 + x11 + x9 + x8 + x4 + x3

Find r0 = a0 % b0

r0 = b0000000000000000001100101100110100110111001001011000111000010111
r0 = 0x000032cd37258e17
r0 = x45 + x44 + x41 + x39 + x38 + x35 + x34 + x32 + x29 + x28 + x26 + x25 + x24 + x21 + x18 + x16 + x15 + x11 + x10 + x9 + x4 + x2 + x + 1

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

a1 = b0
a1 = b0000000000000000010000110000110000001110100101100010101100011000
a1 = 0x0000430c0e962b18
a1 = x46 + x41 + x40 + x35 + x34 + x27 + x26 + x25 + x23 + x20 + x18 + x17 + x13 + x11 + x9 + x8 + x4 + x3

b1 = r0
b1 = b0000000000000000001100101100110100110111001001011000111000010111
b1 = 0x000032cd37258e17
b1 = x45 + x44 + x41 + x39 + x38 + x35 + x34 + x32 + x29 + x28 + x26 + x25 + x24 + x21 + x18 + x16 + x15 + x11 + x10 + x9 + x4 + x2 + x + 1

Find r1 = a1 % b1

r1 = b0000000000000000000101000101101101010111111110001011100100100001
r1 = 0x0000145b57f8b921
r1 = x44 + x42 + x38 + x36 + x35 + x33 + x32 + x30 + x28 + x26 + x25 + x24 + x23 + x22 + x21 + x20 + x19 + x15 + x13 + x12 + x11 + x8 + x5 + 1

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

a2 = b1
a2 = b0000000000000000001100101100110100110111001001011000111000010111
a2 = 0x000032cd37258e17
a2 = x45 + x44 + x41 + x39 + x38 + x35 + x34 + x32 + x29 + x28 + x26 + x25 + x24 + x21 + x18 + x16 + x15 + x11 + x10 + x9 + x4 + x2 + x + 1

b2 = r1
b2 = b0000000000000000000101000101101101010111111110001011100100100001
b2 = 0x0000145b57f8b921
b2 = x44 + x42 + x38 + x36 + x35 + x33 + x32 + x30 + x28 + x26 + x25 + x24 + x23 + x22 + x21 + x20 + x19 + x15 + x13 + x12 + x11 + x8 + x5 + 1

Find r2 = a2 % b2

r2 = b0000000000000000000011100010000011001111001011000100010101110100
r2 = 0x00000e20cf2c4574
r2 = x43 + x42 + x41 + x37 + x31 + x30 + x27 + x26 + x25 + x24 + x21 + x19 + x18 + x14 + x10 + x8 + x6 + x5 + x4 + x2

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

a3 = b2
a3 = b0000000000000000000101000101101101010111111110001011100100100001
a3 = 0x0000145b57f8b921
a3 = x44 + x42 + x38 + x36 + x35 + x33 + x32 + x30 + x28 + x26 + x25 + x24 + x23 + x22 + x21 + x20 + x19 + x15 + x13 + x12 + x11 + x8 + x5 + 1

b3 = r2
b3 = b0000000000000000000011100010000011001111001011000100010101110100
b3 = 0x00000e20cf2c4574
b3 = x43 + x42 + x41 + x37 + x31 + x30 + x27 + x26 + x25 + x24 + x21 + x19 + x18 + x14 + x10 + x8 + x6 + x5 + x4 + x2

Find r3 = a3 % b3

r3 = b0000000000000000000001100011101000000110100011000111011010111101
r3 = 0x0000063a068c76bd
r3 = x42 + x41 + x37 + x36 + x35 + x33 + x26 + x25 + x23 + x19 + x18 + x14 + x13 + x12 + x10 + x9 + x7 + x5 + x4 + x3 + x2 + 1

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

a4 = b3
a4 = b0000000000000000000011100010000011001111001011000100010101110100
a4 = 0x00000e20cf2c4574
a4 = x43 + x42 + x41 + x37 + x31 + x30 + x27 + x26 + x25 + x24 + x21 + x19 + x18 + x14 + x10 + x8 + x6 + x5 + x4 + x2

b4 = r3
b4 = b0000000000000000000001100011101000000110100011000111011010111101
b4 = 0x0000063a068c76bd
b4 = x42 + x41 + x37 + x36 + x35 + x33 + x26 + x25 + x23 + x19 + x18 + x14 + x13 + x12 + x10 + x9 + x7 + x5 + x4 + x3 + x2 + 1

Find r4 = a4 % b4

r4 = b0000000000000000000000100101010011000010001101001010100000001110
r4 = 0x00000254c234a80e
r4 = x41 + x38 + x36 + x34 + x31 + x30 + x25 + x21 + x20 + x18 + x15 + x13 + x11 + x3 + x2 + x

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

a5 = b4
a5 = b0000000000000000000001100011101000000110100011000111011010111101
a5 = 0x0000063a068c76bd
a5 = x42 + x41 + x37 + x36 + x35 + x33 + x26 + x25 + x23 + x19 + x18 + x14 + x13 + x12 + x10 + x9 + x7 + x5 + x4 + x3 + x2 + 1

b5 = r4
b5 = b0000000000000000000000100101010011000010001101001010100000001110
b5 = 0x00000254c234a80e
b5 = x41 + x38 + x36 + x34 + x31 + x30 + x25 + x21 + x20 + x18 + x15 + x13 + x11 + x3 + x2 + x

Find r5 = a5 % b5

r5 = b0000000000000000000000001100011101000000110100011000111010101111
r5 = 0x000000c740d18eaf
r5 = x39 + x38 + x34 + x33 + x32 + x30 + x23 + x22 + x20 + x16 + x15 + x11 + x10 + x9 + x7 + x5 + x3 + x2 + x + 1

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

a6 = b5
a6 = b0000000000000000000000100101010011000010001101001010100000001110
a6 = 0x00000254c234a80e
a6 = x41 + x38 + x36 + x34 + x31 + x30 + x25 + x21 + x20 + x18 + x15 + x13 + x11 + x3 + x2 + x

b6 = r5
b6 = b0000000000000000000000001100011101000000110100011000111010101111
b6 = 0x000000c740d18eaf
b6 = x39 + x38 + x34 + x33 + x32 + x30 + x23 + x22 + x20 + x16 + x15 + x11 + x10 + x9 + x7 + x5 + x3 + x2 + x + 1

Find r6 = a6 % b6

r6 = b0000000000000000000000000000000000000000000000000000000101000011
r6 = 0x0000000000000143
r6 = x8 + x6 + x + 1

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

a7 = b6
a7 = b0000000000000000000000001100011101000000110100011000111010101111
a7 = 0x000000c740d18eaf
a7 = x39 + x38 + x34 + x33 + x32 + x30 + x23 + x22 + x20 + x16 + x15 + x11 + x10 + x9 + x7 + x5 + x3 + x2 + x + 1

b7 = r6
b7 = b0000000000000000000000000000000000000000000000000000000101000011
b7 = 0x0000000000000143
b7 = x8 + x6 + x + 1

Find r7 = a7 % b7

r7 = b0000000000000000000000000000000000000000000000000000000000000000
r7 = 0x0000000000000000
r7 = 0

r7 is zero, so c=gcd(a,b)=b7

c = b0000000000000000000000000000000000000000000000000000000101000011
c = 0x0000000000000143
c = x8 + x6 + x + 1

See also: