Irreducible Polynomials Which Divide Trinomials over Gf (2): Theorems, Results, Applications

Shift-register sequences, also known as pseudorandom sequences, or pseudonoise sequences, have played increasingly important roles in many important applications. The simplest linear feedback shift registers to generate binary sequences involve only two taps, which corresponds to a trinomial over GF(2). It is therefore of interest to know which irreducible polynomials f(x) divide trinomials over GF(2), since the output sequences corresponding to f(x) can be obtained from a two-tap linear feedback shift register (with a suitable initial state) if and only if f(x) divides some trinomial over GF(2). In this work we develop the theory of irreducible polynomials which do, or do not, divide trinomials over GF(2). Then some related problems such as Artin's conjecture about primitive roots, and the conjectures of Blake, Gao and Lambert, and of Tromp, Zhang and Zhao are discussed.