Feedback Shift Registers, Combiners With Memory, and 2-Adic Span

Journal of Cryptology 10 (1997) 111-147.

Andrew Klapper, 779A Anderson Hall, Dept. of Computer Science, University of Kentucky, Lexington, KY, 40506-0046, klapper at
Mark Goresky, Institute for Advanced Study.

Abstract Pseudorandom sequences generated by feedback shift registers with carry operation (FCSR's) are described and analyzed. An analog of the Berlekamp-Massey algorithm is presented which, for any pseudorandom sequence, constructs the smallest FCSR which will generate the sequence. These techniques are used to attack the summation cipher. This analysis gives a unified approach to the study of pseudorandom sequences, arithmetic codes, combiners with memory, and certain new pseudorandom number generators.

Index Terms -- Binary sequences, shift registers, combiners with memory, cryptanalysis, 2-adic numbers, arithmetic codes, 1/q sequences, linear span.