###
Register Synthesis for Algebraic Feedback Shift Registers
Based on Non-Primes

Designs, Codes, and Cryptography, ** 31** (2004) 227-250.
Authors:

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

Jinzhong Xu, University of Kentucky

**Abstract**
In this paper, we describe a solution to the register synthesis problem for
a class of sequence generators known as {\em Algebraic Feedback Shift Registers}
(or AFSRs). These registers are based on the algebra of $\pi$-adic numbers,
where $\pi$ is an element in a ring $R$, and produce sequences of elements
in $R/(\pi)$. We give several cases where the register synthesis problem
can be solved by an efficient algorithm. Consequently, any keystreams
over $R/(\pi)$ used in stream ciphers must be unable to be generated by a
small register in these classes. This paper extends the analyses of feedback
with carry shift registers and algebraic feedback shift registers by Goresky,
Klapper, and Xu.

**Index Terms --**
Feedback shift register, pseudorandom generator,
stream cipher, register synthesis, $N$-adic numbers.