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 = b0000000000000000010100010100010000010000010001010101000100010101
b0 = 0x0000514410455115
b0 = x46 + x44 + x40 + x38 + x34 + x28 + x22 + x18 + x16 + x14 + x12 + x8 + x4 + x2 + 1
Find r0 = a0 % b0
r0 = b0000000000000000000001000001010100010100010100000000000000000000
r0 = 0x0000041514500000
r0 = x42 + x36 + x34 + x32 + x28 + x26 + x22 + x20
r0 is not zero nor one, so continue...
a1 = b0
a1 = b0000000000000000010100010100010000010000010001010101000100010101
a1 = 0x0000514410455115
a1 = x46 + x44 + x40 + x38 + x34 + x28 + x22 + x18 + x16 + x14 + x12 + x8 + x4 + x2 + 1
b1 = r0
b1 = b0000000000000000000001000001010100010100010100000000000000000000
b1 = 0x0000041514500000
b1 = x42 + x36 + x34 + x32 + x28 + x26 + x22 + x20
Find r1 = a1 % b1
r1 = b0000000000000000000000000100000100000100000001010101000100010101
r1 = 0x0000004104055115
r1 = x38 + x32 + x26 + x18 + x16 + x14 + x12 + x8 + x4 + x2 + 1
r1 is not zero nor one, so continue...
a2 = b1
a2 = b0000000000000000000001000001010100010100010100000000000000000000
a2 = 0x0000041514500000
a2 = x42 + x36 + x34 + x32 + x28 + x26 + x22 + x20
b2 = r1
b2 = b0000000000000000000000000100000100000100000001010101000100010101
b2 = 0x0000004104055115
b2 = x38 + x32 + x26 + x18 + x16 + x14 + x12 + x8 + x4 + x2 + 1
Find r2 = a2 % b2
r2 = b0000000000000000000000000000010101010100000001010001000101010000
r2 = 0x0000000554051150
r2 = x34 + x32 + x30 + x28 + x26 + x18 + x16 + x12 + x8 + x6 + x4
r2 is not zero nor one, so continue...
a3 = b2
a3 = b0000000000000000000000000100000100000100000001010101000100010101
a3 = 0x0000004104055115
a3 = x38 + x32 + x26 + x18 + x16 + x14 + x12 + x8 + x4 + x2 + 1
b3 = r2
b3 = b0000000000000000000000000000010101010100000001010001000101010000
b3 = 0x0000000554051150
b3 = x34 + x32 + x30 + x28 + x26 + x18 + x16 + x12 + x8 + x6 + x4
Find r3 = a3 % b3
r3 = b0000000000000000000000000000000100010100010000000000000101010101
r3 = 0x0000000114400155
r3 = x32 + x28 + x26 + x22 + x8 + x6 + x4 + x2 + 1
r3 is not zero nor one, so continue...
a4 = b3
a4 = b0000000000000000000000000000010101010100000001010001000101010000
a4 = 0x0000000554051150
a4 = x34 + x32 + x30 + x28 + x26 + x18 + x16 + x12 + x8 + x6 + x4
b4 = r3
b4 = b0000000000000000000000000000000100010100010000000000000101010101
b4 = 0x0000000114400155
b4 = x32 + x28 + x26 + x22 + x8 + x6 + x4 + x2 + 1
Find r4 = a4 % b4
r4 = b0000000000000000000000000000000000010001010001010001010101010001
r4 = 0x0000000011451551
r4 = x28 + x24 + x22 + x18 + x16 + x12 + x10 + x8 + x6 + x4 + 1
r4 is not zero nor one, so continue...
a5 = b4
a5 = b0000000000000000000000000000000100010100010000000000000101010101
a5 = 0x0000000114400155
a5 = x32 + x28 + x26 + x22 + x8 + x6 + x4 + x2 + 1
b5 = r4
b5 = b0000000000000000000000000000000000010001010001010001010101010001
b5 = 0x0000000011451551
b5 = x28 + x24 + x22 + x18 + x16 + x12 + x10 + x8 + x6 + x4 + 1
Find r5 = a5 % b5
r5 = b0000000000000000000000000000000000000000000100010101010001000101
r5 = 0x0000000000115445
r5 = x20 + x16 + x14 + x12 + x10 + x6 + x2 + 1
r5 is not zero nor one, so continue...
a6 = b5
a6 = b0000000000000000000000000000000000010001010001010001010101010001
a6 = 0x0000000011451551
a6 = x28 + x24 + x22 + x18 + x16 + x12 + x10 + x8 + x6 + x4 + 1
b6 = r5
b6 = b0000000000000000000000000000000000000000000100010101010001000101
b6 = 0x0000000000115445
b6 = x20 + x16 + x14 + x12 + x10 + x6 + x2 + 1
Find r6 = a6 % b6
r6 = b0000000000000000000000000000000000000000000000000000010000010100
r6 = 0x0000000000000414
r6 = x10 + x4 + x2
r6 is not zero nor one, so continue...
a7 = b6
a7 = b0000000000000000000000000000000000000000000100010101010001000101
a7 = 0x0000000000115445
a7 = x20 + x16 + x14 + x12 + x10 + x6 + x2 + 1
b7 = r6
b7 = b0000000000000000000000000000000000000000000000000000010000010100
b7 = 0x0000000000000414
b7 = x10 + x4 + x2
Find r7 = a7 % b7
r7 = b0000000000000000000000000000000000000000000000000000000101000101
r7 = 0x0000000000000145
r7 = x8 + x6 + x2 + 1
r7 is not zero nor one, so continue...
a8 = b7
a8 = b0000000000000000000000000000000000000000000000000000010000010100
a8 = 0x0000000000000414
a8 = x10 + x4 + x2
b8 = r7
b8 = b0000000000000000000000000000000000000000000000000000000101000101
b8 = 0x0000000000000145
b8 = x8 + x6 + x2 + 1
Find r8 = a8 % b8
r8 = b0000000000000000000000000000000000000000000000000000000001000101
r8 = 0x0000000000000045
r8 = x6 + x2 + 1
r8 is not zero nor one, so continue...
a9 = b8
a9 = b0000000000000000000000000000000000000000000000000000000101000101
a9 = 0x0000000000000145
a9 = x8 + x6 + x2 + 1
b9 = r8
b9 = b0000000000000000000000000000000000000000000000000000000001000101
b9 = 0x0000000000000045
b9 = x6 + x2 + 1
Find r9 = a9 % b9
r9 = b0000000000000000000000000000000000000000000000000000000000010100
r9 = 0x0000000000000014
r9 = x4 + x2
r9 is not zero nor one, so continue...
a10 = b9
a10 = b0000000000000000000000000000000000000000000000000000000001000101
a10 = 0x0000000000000045
a10 = x6 + x2 + 1
b10 = r9
b10 = b0000000000000000000000000000000000000000000000000000000000010100
b10 = 0x0000000000000014
b10 = x4 + x2
Find r10 = a10 % b10
r10 = b0000000000000000000000000000000000000000000000000000000000000001
r10 = 0x0000000000000001
r10 = 1
r10 is one, so gcd(a,b) is one (i.e. coprime/relatively prime)
See also: