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

Journal of Cryptology ** 10 ** (1997)
111-147.
Authors:

Andrew Klapper, 779A Anderson Hall, Dept. of Computer Science, University
of Kentucky, Lexington, KY, 40506-0046, klapper at cs.uky.edu.

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.