| 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 t( x) = xm + xa + 1 over GF(2).; In this thesis we develop the theory of irreducible polynomials which do, or do not, divide trinomials over GF(2). Abundant theorems and results are presented relating to the primitivity t and the index r, which is the number of irreducible factors of the t th cyclotomic polynomial phit( x) over GF(2). The set of all positive (odd) integers t such that the irreducible polynomials of odd primitivity t > 1 divide trinomials over GF(2) form a multiplicative module M, which is closed with respect to multiplication by odd numbers. The set G of generators of M is quite sparse, and its members seem related to numbers of the form phin(2).; The distribution of the values of r among the set of all odd primes p leads to a generalization of Artin's Conjecture concerning primitive roots modulo p. We generalized the conjectures of Blake, Gao and Lambert, and of Tromp, Zhang and Zhao, and proved the generalization of the Blake, Gao and Lambert conjecture. |
