摘要
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 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 〉 LCD is also presented.
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 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 〉 LCD is also presented.
基金
supported by the National Natural Science Foundation of China (10871068)
