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.