Feedback shift register (FSR) sequences have been widely used as synchronization, masking, or scrambling codes and for white noise signals in communication systems, signal sets in CDMA communications, key stream generators in stream cipher cryptosystems, random number generators in many cryptographic primitive algorithms, and testing vectors in hardware design. Golomb s popular book Shift Register Sequences, first published in 1967 and revised in 1982 is a pioneering book that discusses this type of sequences. In this chapter, we introduce this topic and discuss the synthesis and the analysis of periodicity of linear feedback shift register sequences. We give different (though equivalent) definitions and representations for LFSR sequences and point out which are most suitable for either implementation or analysis. This chapter contains seven sections, which are organized as follows. In Section 4.1, we give a general description for feedback shift registers at the gate level for the binary case and as a finite field configuration for the q-ary case. In Sections 4.2 4.4, we introduce the definition of LFSR sequences from the point of view of polynomial rings and discuss their characteristic polynomials, minimal polynomials, and periods. Then, we show the decomposition of LFSR sequences. We provide the matrix representation of LFSR sequences in Section 4.5 as another historic approach and discuss their trace representation for the irreducible case in detail in Section 4.6, which is a more modern approach. (The general case will be treated in Chapter 6.) LFSRs with primitive minimal polynomials are basic building blocks for nonlinear...