gf(2) Calculating the gcd (greatest common divisor)
Euclid's Algorithm
c = gcd(a0,b0)
a0 = b0000110010101110101000111111010001111111111000000000000000110011
a0 = 0x0caea3f47fe00033
a0 = x59 + x58 + x55 + x53 + x51 + x50 + x49 + x47 + x45 + x41 + x40 + x39 + x38 + x37 + x36 + x34 + x30 + x29 + x28 + x27 + x26 + x25 + x24 + x23 + x22 + x21 + x5 + x4 + x + 1
b0 = b0000010001010101010100010101000000010101010100000000000000010001
b0 = 0x0455515015500011
b0 = x58 + x54 + x52 + x50 + x48 + x46 + x44 + x40 + x38 + x36 + x28 + x26 + x24 + x22 + x20 + x4 + 1
Find r0 = a0 % b0
r0 = b0000000001010001010100000000010001000000000100000000000000000000
r0 = 0x0051500440100000
r0 = x54 + x52 + x48 + x46 + x44 + x34 + x30 + x20
r0 is not zero nor one, so continue...
a1 = b0
a1 = b0000010001010101010100010101000000010101010100000000000000010001
a1 = 0x0455515015500011
a1 = x58 + x54 + x52 + x50 + x48 + x46 + x44 + x40 + x38 + x36 + x28 + x26 + x24 + x22 + x20 + x4 + 1
b1 = r0
b1 = b0000000001010001010100000000010001000000000100000000000000000000
b1 = 0x0051500440100000
b1 = x54 + x52 + x48 + x46 + x44 + x34 + x30 + x20
Find r1 = a1 % b1
r1 = b0000000000000101000100010000010100010100000100000000000000010001
r1 = 0x0005110514100011
r1 = x50 + x48 + x44 + x40 + x34 + x32 + x28 + x26 + x20 + x4 + 1
r1 is not zero nor one, so continue...
a2 = b1
a2 = b0000000001010001010100000000010001000000000100000000000000000000
a2 = 0x0051500440100000
a2 = x54 + x52 + x48 + x46 + x44 + x34 + x30 + x20
b2 = r1
b2 = b0000000000000101000100010000010100010100000100000000000000010001
b2 = 0x0005110514100011
b2 = x50 + x48 + x44 + x40 + x34 + x32 + x28 + x26 + x20 + x4 + 1
Find r2 = a2 % b2
r2 = b0000000000000000010000000101010100000001000100000000000100010000
r2 = 0x0000405501100110
r2 = x46 + x38 + x36 + x34 + x32 + x24 + x20 + x8 + x4
r2 is not zero nor one, so continue...
a3 = b2
a3 = b0000000000000101000100010000010100010100000100000000000000010001
a3 = 0x0005110514100011
a3 = x50 + x48 + x44 + x40 + x34 + x32 + x28 + x26 + x20 + x4 + 1
b3 = r2
b3 = b0000000000000000010000000101010100000001000100000000000100010000
b3 = 0x0000405501100110
b3 = x46 + x38 + x36 + x34 + x32 + x24 + x20 + x8 + x4
Find r3 = a3 % b3
r3 = b0000000000000000000101010000000100000001010100000001010101010001
r3 = 0x0000150101501551
r3 = x44 + x42 + x40 + x32 + x24 + x22 + x20 + x12 + x10 + x8 + x6 + x4 + 1
r3 is not zero nor one, so continue...
a4 = b3
a4 = b0000000000000000010000000101010100000001000100000000000100010000
a4 = 0x0000405501100110
a4 = x46 + x38 + x36 + x34 + x32 + x24 + x20 + x8 + x4
b4 = r3
b4 = b0000000000000000000101010000000100000001010100000001010101010001
b4 = 0x0000150101501551
b4 = x44 + x42 + x40 + x32 + x24 + x22 + x20 + x12 + x10 + x8 + x6 + x4 + 1
Find r4 = a4 % b4
r4 = b0000000000000000000000010101000000000101000000000100000100000101
r4 = 0x0000015005004105
r4 = x40 + x38 + x36 + x26 + x24 + x14 + x8 + x2 + 1
r4 is not zero nor one, so continue...
a5 = b4
a5 = b0000000000000000000101010000000100000001010100000001010101010001
a5 = 0x0000150101501551
a5 = x44 + x42 + x40 + x32 + x24 + x22 + x20 + x12 + x10 + x8 + x6 + x4 + 1
b5 = r4
b5 = b0000000000000000000000010101000000000101000000000100000100000101
b5 = 0x0000015005004105
b5 = x40 + x38 + x36 + x26 + x24 + x14 + x8 + x2 + 1
Find r5 = a5 % b5
r5 = b0000000000000000000000000000000101010001010101000000010100000001
r5 = 0x0000000151540501
r5 = x32 + x30 + x28 + x24 + x22 + x20 + x18 + x10 + x8 + 1
r5 is not zero nor one, so continue...
a6 = b5
a6 = b0000000000000000000000010101000000000101000000000100000100000101
a6 = 0x0000015005004105
a6 = x40 + x38 + x36 + x26 + x24 + x14 + x8 + x2 + 1
b6 = r5
b6 = b0000000000000000000000000000000101010001010101000000010100000001
b6 = 0x0000000151540501
b6 = x32 + x30 + x28 + x24 + x22 + x20 + x18 + x10 + x8 + 1
Find r6 = a6 % b6
r6 = b0000000000000000000000000000000000000000010100010100010100000100
r6 = 0x0000000000514504
r6 = x22 + x20 + x16 + x14 + x10 + x8 + x2
r6 is not zero nor one, so continue...
a7 = b6
a7 = b0000000000000000000000000000000101010001010101000000010100000001
a7 = 0x0000000151540501
a7 = x32 + x30 + x28 + x24 + x22 + x20 + x18 + x10 + x8 + 1
b7 = r6
b7 = b0000000000000000000000000000000000000000010100010100010100000100
b7 = 0x0000000000514504
b7 = x22 + x20 + x16 + x14 + x10 + x8 + x2
Find r7 = a7 % b7
r7 = b0000000000000000000000000000000000000000000100010101010000000001
r7 = 0x0000000000115401
r7 = x20 + x16 + x14 + x12 + x10 + 1
r7 is not zero nor one, so continue...
a8 = b7
a8 = b0000000000000000000000000000000000000000010100010100010100000100
a8 = 0x0000000000514504
a8 = x22 + x20 + x16 + x14 + x10 + x8 + x2
b8 = r7
b8 = b0000000000000000000000000000000000000000000100010101010000000001
b8 = 0x0000000000115401
b8 = x20 + x16 + x14 + x12 + x10 + 1
Find r8 = a8 % b8
r8 = b0000000000000000000000000000000000000000000001010100000100000001
r8 = 0x0000000000054101
r8 = x18 + x16 + x14 + x8 + 1
r8 is not zero nor one, so continue...
a9 = b8
a9 = b0000000000000000000000000000000000000000000100010101010000000001
a9 = 0x0000000000115401
a9 = x20 + x16 + x14 + x12 + x10 + 1
b9 = r8
b9 = b0000000000000000000000000000000000000000000001010100000100000001
b9 = 0x0000000000054101
b9 = x18 + x16 + x14 + x8 + 1
Find r9 = a9 % b9
r9 = b0000000000000000000000000000000000000000000000010001000100000100
r9 = 0x0000000000011104
r9 = x16 + x12 + x8 + x2
r9 is not zero nor one, so continue...
a10 = b9
a10 = b0000000000000000000000000000000000000000000001010100000100000001
a10 = 0x0000000000054101
a10 = x18 + x16 + x14 + x8 + 1
b10 = r9
b10 = b0000000000000000000000000000000000000000000000010001000100000100
b10 = 0x0000000000011104
b10 = x16 + x12 + x8 + x2
Find r10 = a10 % b10
r10 = b0000000000000000000000000000000000000000000000000001010000010101
r10 = 0x0000000000001415
r10 = x12 + x10 + x4 + x2 + 1
r10 is not zero nor one, so continue...
a11 = b10
a11 = b0000000000000000000000000000000000000000000000010001000100000100
a11 = 0x0000000000011104
a11 = x16 + x12 + x8 + x2
b11 = r10
b11 = b0000000000000000000000000000000000000000000000000001010000010101
b11 = 0x0000000000001415
b11 = x12 + x10 + x4 + x2 + 1
Find r11 = a11 % b11
r11 = b0000000000000000000000000000000000000000000000000000000000000000
r11 = 0x0000000000000000
r11 = 0
r11 is zero, so c=gcd(a,b)=b11
c = b0000000000000000000000000000000000000000000000000001010000010101
c = 0x0000000000001415
c = x12 + x10 + x4 + x2 + 1
See also: