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.