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 qn − 1 constructed by Chan and Games [1-2] (q is a prime power pm, p is an odd prime) with the maximal possible linear complexity qn − 1 when considered as sequences over GF(2). This indicates that binary sequences with high GF(2) linear complexities LC2 and low GF(p)-linear complexities LCp 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 LC2 > LCp is also presented.