The Asymptotic Behavior of N-Adic Complexity

Appeared in: Workshop on Codes and Cryptography (WCC), Bergen 2005. 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

Abstract We study the asymptotic behavior of stream cipher security measures associated with classes of sequence generators such as linear feedback shift registers and feedback with carry shift registers. For nonperiodic sequences we consider normalized measures and study the set of accumulation points for a fixed sequence. We see that the the set of accumulation points is always a closed subinterval of [0,1]. For FCSRs we see that this interval is of the form [B,1-B], a result that is an analog of an earlier result by Dai, Jiang, Imamura, and Gong for LFSRs. We also see that all such intervals occur for infinitely many sequences.

Index Terms -- Pseudorandom sequence, stream cipher, feedback with carry shift register, asymptotic behavior.