Finding GCD of two polynomial over field F2 (ield of integer residues modulo 2)

Question

I am trying to find GCD of the following polynomials ( two separate questions ) in Field modulo 2 and field modulo 3. But I am stuck in the first one for some reasons.

a(x) =x5+x3+x2+ 1,
b(x) =x3+x         for mod 2


a(x) = 2x3+2x2+x+1
b(x) =x2+2           for mod 3

For the first one, I tried to represent the polynomials as bits of 1's and 0's (e.g : 101101 and 1010) and tried to find GCD using Euclid's algorithm, but at some point it leads to zero, which is not possible if I am doing the calculation correctly.

2nd set of polynomials, I am not sure at all, as it as co efficients more than 1.

Any help would be much appreciated.

Answer 1

Let

f_1 = x^5 + x^3 + x^2 + 1 and

f_2 = x^3 + x

Working mod 2 we can change the notation to

f_1 = (1,0,1,1,0,1) and

f_2 = (1,0,1,0).

Doing long division we get that f_1 = q_2 * f_2 + f_3 where f_3 is of degree strictly less than the degree of f_2.

It turns out that

q_2 = (1,0,0) that is q_2 = x^2

f_3 = (1,0,1) that is f_3 = x^2 + 1

Continuing we get

f_2 = q_3 * f_3 + f_4

It turns out that

q_3 = (1,0) and

f_4 = (0)

That latter signals that Euclid's algorithm is done and the last non-zero polynomial among the f_n's is the GCD. Thus f_3 is the GCD. It is straight forward to show that f_3 is indeed a common divisor.

For the second case you work with tuples, like the (1,0,1) above, but this time the coordinates are 0, 1 or 2 (the remainders mod 3). Otherwise the algorithm is identical.

It would increase your understanding if you implemented your algorithm in some programming language.