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.
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.