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 i...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)
文摘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.
