Irreducible Polynomials Which Divide Trinomials

The simplest linear shift registers to generate binary sequences involve only two taps, which corresponds to a trinomial over GF . It is therefore of interest to know which irreducible polynomials divide trinomials over GF , since the output sequences corresponding to can be obtained from a two-tap linear feedback shift register (with a suitable initial state) if and only if divides some trinomial over GF . In this paper, we develop the theory of which irreducible polynomials do, or do not, divide trinomials over GF . Then some related problems such as Artin's conjecture about primitive roots, and the conjectures of Blake, Gao, and Lambert, as well as of Tromp, Zhang, and Zhao are discussed. Index Terms—Irreducible polynomial, linear feedback shift reg- ister sequence, primitive polynomial, trinomial.