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.