### Algebraic Feedback Shift Registers

Theoretical Computer Science ** 226 ** (1999) 61-93.
Author:

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

Jinzhong Xu, University of Kentucky

**Abstract**
A general framework for the design of feedback registers based on algebra
over complete rings is described. These registers generalize linear
feedback shift registers and feedback with carry shift registers. Basic properties of the output sequences are studied: relations to the algebra of
the underlying ring; synthesis of the register from the sequence (which
has implications for cryptanalysis); and basic statistical properties. These
considerations lead to security measures for stream ciphers, analogous to
the notion of linear complexity that arises from linear feedback shift
registers. We also show that when the underlying ring is a polynomial
ring over a finite field, the new registers can be simulated by linear
feedback shift registers with small nonlinear filters.

**Index Terms --**
cryptography; feedback shift register; complete ring;
stream cipher; pseudo-random number generator.