Abstract: This paper studies the k-error linear complexity of binary sequences with period 2n. It is well known that the linear complexity of binary sequences with period 2n is strictly larger than 2n1. Form the entire stability of binary periodic sequences, the minimal value k is given for which there are at least half of the sequences with period 2n have k-error linear complexity not larger than 2n1. The minimal value k is studied for balanced sequences and imbalanced sequences with period 2n respectively.

Key words: stream cipher, linear complexity, k-error linear complexity

摘要： 讨论周期为2n的二元序列k-错误线性复杂度问题。周期为2n的二元序列线性复杂度严格大于2n1。从二元周期序列的整体稳定性开始给出最小的k，使得全体周期为2n的二元序列中至少有一半序列的k-错误线性复杂度不大于2n1。对全体周期为2n的平衡序列和非平衡序列分别进行研究，给出相应最小的k。

关键词: 序列密码, 线性复杂度, k-错误线性复杂度

CLC Number: 

• TN918.1