Algebraic Shift Register Sequences

By Mark Goresky, Institute for Advanced Study

e-mail: goresky at math dot ias dot edu Home Page


Andrew Klapper, University of Kentucky

e-mail: klapper at cs dot uky dot edu Home Page

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.

This page translated into Romanian (by Alexandra Seremina).

Table of Contents

    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.3 Initial loading
        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.2 N-Adic numbers
        4.3 Analysis of FCSRs 
        4.4 Initial Loading 
        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.2 pi-Adic numbers
        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.7 The Diaconis mind-reader
        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.1 N-adic span and complexity
        16.2 Symmetric N-adic span
        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.5 Asymptotic N-adic 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;