Question

The GCD of x^3+ x + 1 and x^2 + x + 1 over GF(2) is

(a) 1

(b) x + 1

(c) x^2

(d) x^2 + 1

I have been asked this question during an online exam.

Query is from Polynomial and Modular Arithmetic- IV topic in chapter Basic Concepts in Number Theory and Finite Fields of Cryptograph & Network Security

Answer 1

To determine the GCD of the polynomials x3+x+1x^3 + x + 1x3+x+1 and x2+x+1x^2 + x + 1x2+x+1 over the finite field GF(2)GF(2)GF(2), we will use polynomial division and the Euclidean algorithm.

Step 1: Understand the field GF(2)GF(2)GF(2)

In GF(2)GF(2)GF(2), the arithmetic is modulo 2, meaning:

• 1+1=01 + 1 = 01+1=0
• 1×1=11 \times 1 = 11×1=1
• 0+0=00 + 0 = 00+0=0

Step 2: Perform polynomial division

We need to divide x3+x+1x^3 + x + 1x3+x+1 by x2+x+1x^2 + x + 1x2+x+1 over GF(2)GF(2)GF(2).

Division process:

1. Divide the leading term: x3x^3x3 by x2x^2x2, which gives xxx.
2. Multiply: x⋅(x2+x+1)=x3+x2+xx \cdot (x^2 + x + 1) = x^3 + x^2 + xx⋅(x2+x+1)=x3+x2+x.
3. Subtract (remember, subtraction is the same as addition in GF(2)GF(2)GF(2)): (x3+x+1)−(x3+x2+x)=x2+1.(x^3 + x + 1) - (x^3 + x^2 + x) = x^2 + 1.(x3+x+1)−(x3+x2+x)=x2+1.
4. Divide the leading term: x2x^2x2 by x2x^2x2, which gives 111.
5. Multiply: 1⋅(x2+x+1)=x2+x+11 \cdot (x^2 + x + 1) = x^2 + x + 11⋅(x2+x+1)=x2+x+1.
6. Subtract: (x2+1)−(x2+x+1)=x.(x^2 + 1) - (x^2 + x + 1) = x.(x2+1)−(x2+x+1)=x.

Thus, after division, we are left with the remainder xxx, meaning the GCD is the last non-zero remainder.

Step 3: Conclusion

The GCD of x3+x+1x^3 + x + 1x3+x+1 and x2+x+1x^2 + x + 1x2+x+1 over GF(2)GF(2)GF(2) is 1\boxed{1}1​, because we reached a remainder of 1, indicating that the two polynomials are coprime (i.e., they have no common factors other than 1).

Correct Answer:

(a) 1