This a draft of a book on many aspects of algebraic methods of
generating pseudo-random sequences, focusing on properties that
may in communications, especially cryptography and CDMA.
There are many sections that are still in flux and certainly many
errors, so be warned. You are welcome to download the book in its
current state. We ask only that you give us your feedback.
Part I: Algebraic Preliminaries
Chapter 1: Introduction
Chapter 2: Abstract Algebra
2.1 Group Theory
2.2 Rings
2.3 Characters and Fourier
transforms
2.4 Polynomials
2.5 Exercises
Chapter 3: Fields
3.1 Field extensions
3.2 Finite Fields
3.3 Quadratic forms over a finite
field
3.4 Algebraic Number Fields
3.5 Local and global fields
3.6 Exercises
Chapter 4: Finite Rings and Galois Rings
4.1 Finite Local
Rings
4.2
Examples
4.3 Divisibility in
R[x]
4.4 Tools for Local
Rings
4.5 Galois
rings
4.6
Exercises
Chapter 5: Sequences, Power Series and Adic Rings
5.1
Sequences
5.2 Power
Series
5.3 Reciprocal Laurent series
5.4 N-Adic Numbers
5.5 π-Adic
Numbers
5.6 Other constructions
5.7 Continued
Fractions
5.8
Exercises
Part II Algebraically Defined Sequences
Chapter 6: Linear Feedback Shift Registers and
Linear Recurrences
6.1
Definitions
6.2 Matrix description
6.3 Initial loading
6.4 Generating functions
6.5 When the connection
polynomial factors
6.6 Algebraic Models and the ring
R[x]/(q)
6.7 Families of recurring
sequences and ideals
6.8 Examples
6.9 Exercises
Chapter 7: Feedback with Carry Shift Registers and
Multiply with Carry Sequences
7.1 Definitions
7.2 Analysis of FCSRs
7.3 Initial Loading
7.4 Representation of FCSR
Sequences
7.5 Example
7.6 Memory Requirements
7.7 Random Number generation
using MWC
7.8 Exercises
Chapter 8 Algebraic Feedback Shift Registerss
8.1 Definitions
8.2 Properties of AFSRs
8.3 Memory Requirements
8.4 Periodicity
8.5 Exponential Representation
and Period of AFSR Sequences
8.6 Examples
8.7 Exercises
Chapter 9: d-FCSRs
9.1 Binary d-FCSRs
9.2 General d-FCSRs
9.3 Relation Between the Norm and
the Period
9.4 Periodicity
9.5 Elementary description of
d-FCSR sequences
9.6 An Example
9.7 Exercises
Chapter 10: Galois mode and related circuits
10.1 Galois mode LFSRs
10.2 Division by q(x) in R[[x]]
10.3 Galois mode FCSRs
10.4 Division by q in the N-adic
numbers
10.5 Galois mode d-FCSRs
10.6 Linear register
10.7 Exercises
Part III Pseudo-Random and Pseudo-Noise Sequences
Chapter 11: Measures of pseudorandomness
11.1 Why pseudo-random?
11.2 Sequences based on an
arbitrary alphabet
11.3
Correlations
11.4 Exercises
Chapter 12: Shift and add sequences
12.1 Basic properties
12.2 Characterization of shift
and add sequences
12.3 Examples of shift and add sequences
12.4 Further properties of shift
and add sequences
12.5 Proof of Theorem 12.3.1
12.6 Arithmetic Shift and Add
Sequences
12.7 Exercises
Chapter 13: m-Sequences
13.1 Basic properties of
m-sequences
13.2 Decimations
13.3 Interleaved structure
13.4 Fourier transforms and
m-sequences
13.5 Cross-correlation of an
m-sequence and its decimation
13.6 The Diaconis mind-reader
13.7 Exercises
Chapter 14: Related Sequencesi and their Correlations
14.1 Welch bound
14.2 Families derived from a
decimation
14.3 Gold sequences
14.4 Kasami sequences, small set
14.5 Geometric sequences
14.6 GMW sequences
14.7 d-form sequences
14.8 Legendre and Dirichlet
sequences
14.9 Frequency hopping sequences
14.10 Maximal sequences over a
finite local ring ring
14.11 Exercises
Chapter 15: Maximal Period Function Field Sequences
15.1 The Rational function field
AFSR
15.2 Global function
fields
15.3 Exercises
Chapter 16: Maximal Period FCSRs
16.1 l-Sequences
16.2 Distributional properties of
l-sequences
16.3 Arithmetic correlations
16.4 Tables
16.5 Exercises
Chapter 17: Maximal Period d-FCSRs
17.1 Identifying maximal length sequences
17.2 Distribution properties of
d-l-Sequences
17.3 Arithmetic correlation
17.4 Exercises
Part IV Register Synthesis and Security Measures
Chapter 18: Register Synthesis and LFSR Synthesis
18.1 Sequence generators and the
register synthesis problem
18.2 LFSRs and the
Berlekamp-Massey algorithm
18.3 Blahut’s theorem
18.4 The Gunther-Blahut theorem
18.5 Generating sequences with
large linear span
18.6
Exercises
Chapter 19: FCSR Synthesis
19.1 N-adic span and complexity
19.2 Symmetric N-adic span
19.3 Rational approximation
19.4 Exercises
Chapter 20: AFSR Synthesis
20.1 Xu’s rational approximation
algorithm
20.2 Rational approximation in Z
20.3 Proof of correctness
20.4 Rational approximation in
function fields
20.5 Rational approximation in
ramified extensions
20.6 Rational approximation in
quadratic extensions
20.7 Rational approximation by
interleaving
20.8 Rational function fields:
pi-adic vs. linear span
20.9 Exercises
Chapter 21: Average and Asymptotic Behavior of
Security Measures
21.1 Average behavior of linear
complexity
21.2 Average behavior of N-adic
complexity
21.3 Asymptotic behavior of
security measures
21.4 Asymptotic linear complexity
21.5 Asymptotic N-adic complexity
21.6 Consequences and questions
21.7 Exercises