Expected pi-Adic Complexity of Sequences

Authors: Andrew Klapper
Andrew Klapper, 307 Marsbury, Dept. of Computer Science, University of Kentucky, Lexington, KY, 40506-0633, klapper at cs.uky.edu. www.cs.uky.edu/~klapper/andy.html

Appeared in: IEEE Transatcions on Information Theory 56 (2010) 2486 - 250
Abstract Various measures of security of stream ciphers have been studied that are based on the problem of finding a minimum size generator for the keystream in some special class of generators. These include linear and p-adic spans, as well as pi-adic span, which is based on a choice of an element pi in a finite extension of the integers. The corresponding sequence generators are known as linear feedback shift registers, feedback with carry shift registers, and the more general algebraic feedback shift registers, respectively. In this paper the average behavior of such security measures when pi^d= p >0 or pi^2= -p < 0 is studied. In these cases, if \mbbZ[\pi] is the ring of integers in its fraction field and is a UFD, it is shown that the average pi-adic span is n - O(\log(n)) for sequences with period n.

Index Terms -- algebraic feedback shift register, applied abstract algebra, security measure, stream cipher.