On GF(p)-linear complexities of binary sequences

Several geometric sequences have very low linear complexities when considered as sequences over GF( p ), such as the binary sequences of period q n − 1 constructed by Chan and Games [1–2] ( q is a prime power p m , p is an odd prime) with the maximal possible linear complexity q n − 1 when considered as sequences over GF(2). This indicates that binary sequences with high GF(2) linear complexities LC 2 and low GF( p )-linear complexities LC p are not secure for use in stream ciphers. In this article, several lower bounds on the GF( p )-linear complexities of binary sequences is proved and the results are applied to the GF( p )-linear complexities of Blum-Blum-Shub, self-shrinking, and de Bruijn sequences. A lower bound on the number of the binary sequences with LC 2 > LC p is also presented.