gf(2) Calculating the gcd (greatest common divisor)
Euclid's Algorithm
c = gcd(a0,b0)
a0 = b0000000000000000000000000000000000000000000000000000011111011101
a0 = 0x00000000000007dd
a0 = x10 + x9 + x8 + x7 + x6 + x4 + x3 + x2 + 1
b0 = b0000000000000000000000000000000000000000000000000000001001001100
b0 = 0x000000000000024c
b0 = x9 + x6 + x3 + x2
Find r0 = a0 % b0
r0 = b0000000000000000000000000000000000000000000000000000000100001001
r0 = 0x0000000000000109
r0 = x8 + x3 + 1
r0 is not zero nor one, so continue...
a1 = b0
a1 = b0000000000000000000000000000000000000000000000000000001001001100
a1 = 0x000000000000024c
a1 = x9 + x6 + x3 + x2
b1 = r0
b1 = b0000000000000000000000000000000000000000000000000000000100001001
b1 = 0x0000000000000109
b1 = x8 + x3 + 1
Find r1 = a1 % b1
r1 = b0000000000000000000000000000000000000000000000000000000001011110
r1 = 0x000000000000005e
r1 = x6 + x4 + x3 + x2 + x
r1 is not zero nor one, so continue...
a2 = b1
a2 = b0000000000000000000000000000000000000000000000000000000100001001
a2 = 0x0000000000000109
a2 = x8 + x3 + 1
b2 = r1
b2 = b0000000000000000000000000000000000000000000000000000000001011110
b2 = 0x000000000000005e
b2 = x6 + x4 + x3 + x2 + x
Find r2 = a2 % b2
r2 = b0000000000000000000000000000000000000000000000000000000000101111
r2 = 0x000000000000002f
r2 = x5 + x3 + x2 + x + 1
r2 is not zero nor one, so continue...
a3 = b2
a3 = b0000000000000000000000000000000000000000000000000000000001011110
a3 = 0x000000000000005e
a3 = x6 + x4 + x3 + x2 + x
b3 = r2
b3 = b0000000000000000000000000000000000000000000000000000000000101111
b3 = 0x000000000000002f
b3 = x5 + x3 + x2 + x + 1
Find r3 = a3 % b3
r3 = b0000000000000000000000000000000000000000000000000000000000000000
r3 = 0x0000000000000000
r3 = 0
r3 is zero, so c=gcd(a,b)=b3
c = b0000000000000000000000000000000000000000000000000000000000101111
c = 0x000000000000002f
c = x5 + x3 + x2 + x + 1
See also: