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 = b0000000000000000000100011011101100010010111000110111101000001100
b0 = 0x000011bb12e37a0c
b0 = x44 + x40 + x39 + x37 + x36 + x35 + x33 + x32 + x28 + x25 + x23 + x22 + x21 + x17 + x16 + x14 + x13 + x12 + x11 + x9 + x3 + x2
Find r0 = a0 % b0
r0 = b0000000000000000000011100010000011001111001011000100010101111011
r0 = 0x00000e20cf2c457b
r0 = x43 + x42 + x41 + x37 + x31 + x30 + x27 + x26 + x25 + x24 + x21 + x19 + x18 + x14 + x10 + x8 + x6 + x5 + x4 + x3 + x + 1
r0 is not zero nor one, so continue...
a1 = b0
a1 = b0000000000000000000100011011101100010010111000110111101000001100
a1 = 0x000011bb12e37a0c
a1 = x44 + x40 + x39 + x37 + x36 + x35 + x33 + x32 + x28 + x25 + x23 + x22 + x21 + x17 + x16 + x14 + x13 + x12 + x11 + x9 + x3 + x2
b1 = r0
b1 = b0000000000000000000011100010000011001111001011000100010101111011
b1 = 0x00000e20cf2c457b
b1 = x43 + x42 + x41 + x37 + x31 + x30 + x27 + x26 + x25 + x24 + x21 + x19 + x18 + x14 + x10 + x8 + x6 + x5 + x4 + x3 + x + 1
Find r1 = a1 % b1
r1 = b0000000000000000000000111101101001000011100101111011010110000001
r1 = 0x000003da4397b581
r1 = x41 + x40 + x39 + x38 + x36 + x35 + x33 + x30 + x25 + x24 + x23 + x20 + x18 + x17 + x16 + x15 + x13 + x12 + x10 + x8 + x7 + 1
r1 is not zero nor one, so continue...
a2 = b1
a2 = b0000000000000000000011100010000011001111001011000100010101111011
a2 = 0x00000e20cf2c457b
a2 = x43 + x42 + x41 + x37 + x31 + x30 + x27 + x26 + x25 + x24 + x21 + x19 + x18 + x14 + x10 + x8 + x6 + x5 + x4 + x3 + x + 1
b2 = r1
b2 = b0000000000000000000000111101101001000011100101111011010110000001
b2 = 0x000003da4397b581
b2 = x41 + x40 + x39 + x38 + x36 + x35 + x33 + x30 + x25 + x24 + x23 + x20 + x18 + x17 + x16 + x15 + x13 + x12 + x10 + x8 + x7 + 1
Find r2 = a2 % b2
r2 = b0000000000000000000000010100100111000001011100101001001101111111
r2 = 0x00000149c172937f
r2 = x40 + x38 + x35 + x32 + x31 + x30 + x24 + x22 + x21 + x20 + x17 + x15 + x12 + x9 + x8 + x6 + x5 + x4 + x3 + x2 + x + 1
r2 is not zero nor one, so continue...
a3 = b2
a3 = b0000000000000000000000111101101001000011100101111011010110000001
a3 = 0x000003da4397b581
a3 = x41 + x40 + x39 + x38 + x36 + x35 + x33 + x30 + x25 + x24 + x23 + x20 + x18 + x17 + x16 + x15 + x13 + x12 + x10 + x8 + x7 + 1
b3 = r2
b3 = b0000000000000000000000010100100111000001011100101001001101111111
b3 = 0x00000149c172937f
b3 = x40 + x38 + x35 + x32 + x31 + x30 + x24 + x22 + x21 + x20 + x17 + x15 + x12 + x9 + x8 + x6 + x5 + x4 + x3 + x2 + x + 1
Find r3 = a3 % b3
r3 = b0000000000000000000000000000000000000000000000000000000000000000
r3 = 0x0000000000000000
r3 = 0
r3 is zero, so c=gcd(a,b)=b3
c = b0000000000000000000000010100100111000001011100101001001101111111
c = 0x00000149c172937f
c = x40 + x38 + x35 + x32 + x31 + x30 + x24 + x22 + x21 + x20 + x17 + x15 + x12 + x9 + x8 + x6 + x5 + x4 + x3 + x2 + x + 1
See also: