Question

Is x^3 + x^2 + 1 reducible over GF(2)

(a) Yes

(b) No

(c) Can’t Say

(d) Insufficient Data

This question was addressed to me in a national level competition.

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

Answer 1

The correct answer is (b) No

To explain: Irreducible. On factoring this polynomial, one factor is x and the other is (x + 1), which gives us the roots x = 0 or x = 1 respectively. By substitution of 0 and 1 into this polynomial, it clearly has no roots.