# Algebraic Shift Register Sequences

## Andrew Klapper, University of Kentucky

This a book on many aspects of algebraic methods of generating pseudo-random sequences, focusing on properties that may be useful in communications, especially cryptography and CDMA.
Here is the Publisher's website.
Here is Amazon's website.

Chapter 1: Introduction
1.1 Pseudorandom sequences
1.2 LFSR sequences
1.3 FCSR sequences
1.4 Register synthesis
1.5 Applications of pseudorandom sequences
Part I Algebraically Defined Sequences
Chapter 2: Sequences
2.1 Sequences and period
2.2 Fibonacci numbers
2.3 Distinct sequences
2.4 Sequence generators and models
2.5 Exercises
Chapter 3: Linear Feedback Shift Registers and Linear Recurrences
3.1 Definitions
3.2 Matrix description
3.4 Power series
3.5 Generating functions
3.6 When the connection polynomial factors
3.7 Algebraic Models and the ring R[x]/(q)
3.8 Families of recurring sequences and ideals
3.9 Examples
3.10 Exercises
Chapter 4: Feedback with Carry Shift Registers and Multiply with Carry Sequences
4.1 Definitions
4.3 Analysis of FCSRs
4.5 Representation of FCSR Sequences
4.6 Example
4.7 Memory Requirements
4.8 Random Number generation using MWC
4.9 Exercises
Chapter 5 Algebraic Feedback Shift Registerss
5.1 Definitions
5.3 Properties of AFSRs
5.4 Memory Requirements
5.5 Periodicity
5.6 Exponential Representation and Period of AFSR Sequences
5.7 Examples
5.8 Exercises
Chapter 6: d-FCSRs
6.1 Binary d-FCSRs
6.2 General d-FCSRs
6.3 Relation Between the Norm and the Period
6.4 Periodicity
6.5 Elementary description of d-FCSR sequences
6.6 An Example
6.7 Exercises
Chapter 7: Galois mode and related circuits
7.1 Galois mode LFSRs
7.2 Division by q(x) in R[[x]]
7.3 Galois mode FCSRs
7.4 Division by q in the N-adic numbers
7.5 Galois mode d-FCSRs
7.6 Linear register
7.7 Exercises
Part II Pseudo-Random and Pseudo-Noise Sequences
Chapter 8: Measures of pseudorandomness
8.1 Why pseudo-random?
8.2 Sequences based on an arbitrary alphabet
8.3 Correlations
8.4 Exercises
Chapter 9: Shift and add sequences
9.1 Basic properties
9.2 Characterization of shift and add sequences
9.3 Examples of shift and add sequences
9.4 Further properties of shift and add sequences
9.5 Proof of Theorem 9.4.1
9.6 Arithmetic Shift and Add Sequences
12.7 Exercises
Chapter 10: m-Sequences
10.1 Basic properties of m-sequences
10.2 Decimations
10.3 Interleaved structure
10.4 Pseudo-noise arrays
10.5 Fourier transforms and m-sequences
10.6 Cross-correlation of an m-sequence and its decimation
10.8 Exercises
Chapter 11: Related Sequences and their Correlations
11.1 Welch bound
11.2 Families derived from a decimation
11.3 Gold sequences
11.4 Kasami sequences, small set
11.5 Geometric sequences
11.6 GMW sequences
11.7 d-form sequences
11.8 Legendre and Dirichlet sequences
11.9 Frequency hopping sequences
11.10 Optical orthogonal codes
11.11 Maximal sequences over a finite local ring
11.12 Exercises
Chapter 12: Maximal Period Function Field Sequences
12.1 The Rational function field AFSR
12.2 Global function fields
12.3 Exercises
Chapter 13: Maximal Period FCSRs
13.1 l-Sequences
13.2 Distributional properties of l-sequences
13.3 Arithmetic correlations
13.4 Tables
13.5 Exercises
Chapter 14: Maximal Period d-FCSRs
14.1 Identifying maximal length sequences
14.2 Distribution properties of d-l-Sequences
14.3 Exercises
Part III Register Synthesis and Security Measures
Chapter 15: Register Synthesis and LFSR Synthesis
15.1 Sequence generators and the register synthesis problem
15.2 LFSRs and the Berlekamp-Massey algorithm
15.3 Blahut’s theorem
15.4 The Gunther-Blahut theorem
15.5 Generating sequences with large linear span
15.6 Exercises
Chapter 16: FCSR Synthesis
16.3 Rational approximation
16.4 Exercises
Chapter 17: AFSR Synthesis
17.1 Xu’s rational approximation algorithm
17.2 Rational approximation in Z
17.3 Proof of correctness
17.4 Rational approximation in function fields
17.5 Rational approximation in ramified extensions
17.6 Rational approximation in quadratic extensions
17.7 Rational approximation by interleaving
17.8 Rational function fields: pi-adic vs. linear span
17.9 Exercises
Chapter 18: Average and Asymptotic Behavior of Security Measures
18.1 Average behavior of linear complexity
18.2 Average behavior of N-adic complexity
18.3 Asymptotic behavior of security measures
18.4 Asymptotic linear complexity
18.6 Consequences and questions
18.7 Exercises
Part IV: Algebraic Background
Chapter A: Abstract Algebra
A.1 Group Theory
A.2 Rings
A.3 Polynomials
Chapter B: Fields
B.1 Field extensions
B.2 Finite Fields
B.3 Quadratic forms over a finite field
B.4 Algebraic Number Fields
B.5 Local and global fields
Chapter C: Finite Rings and Galois Rings
C.1 Finite Local Rings
C.2 Examples
C.3 Divisibility in R[x]
C.4 Tools for Local Rings
C.5 Galois rings
Chapter D: Algebraic Realizations of Sequences
D.1 Alternate representations of pi-adic numbers
D.2 Continued fractions
D.3 Exercises;