Algebraic Shift Register Sequences

Mark Goresky is a member of the School of Mathematics at the Institute for Advanced Study in Princeton, New Jersey.

Describes the design, mathematical analysis and implementation of pseudo-random sequences for applications in communications, cryptography and simulations.

1. Introduction; Part I. Algebraically Defined Sequences: 2. Sequences; 3. Linear feedback shift registers and linear recurrences; 4. Feedback with carry shift registers and multiply with carry sequences; 5. Algebraic feedback shift registers; 6. d-FCSRs; 7. Galois mode, linear registers, and related circuits; Part II. Pseudo-Random and Pseudo-Noise Sequences: 8. Measures of pseudo-randomness; 9. Shift and add sequences; 10. M-sequences; 11. Related sequences and their correlations; 12. Maximal period function field sequences; 13. Maximal period FCSR sequences; 14. Maximal period d-FCSR sequences; Part III. Register Synthesis and Security Measures: 15. Register synthesis and LFSR synthesis; 16. FCSR synthesis; 17. AFSR synthesis; 18. Average and asymptotic behavior of security measures; Part IV. Algebraic Background: A. Abstract algebra; B. Fields; C. Finite local rings and Galois rings; D. Algebraic realizations of sequences; Bibliography; Index.