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

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

Andrew Klapper, 779A Anderson Hall, Dept. of Computer Science, University of Kentucky, Lexington, KY, 40506-0046, klapper at
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.