On GF(p)-linear complexities of binary sequences  

作　　者：XU Li-qing 

机构地区：[1]Software Engineering Institute, East China Normal University, Shanghai 200062, China

出　　处：《The Journal of China Universities of Posts and Telecommunications》2009年第4期112-115,124,共5页中国邮电高校学报（英文版）

基　　金：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.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.

关 键 词：CRYPTOGRAPHY stream cipher binary sequences GF（2） linear complexity GF（p）-linear complexity 

分 类 号：TN918.1[电子电信—通信与信息系统] TN911.21[电子电信—信息与通信工程]