pn-周期二元序列的线性复杂度与k-错线性复杂度

密码学意义上强的序列不仅应该具有足够高的线性复杂度，而且当少量比特发生变化时不会引起线性复杂度的急剧下降，即具有足够高的k-错线性复杂度．基于x^pn-1在GF(2)上的分解式非常明确和简单的事实，研究了周期为pⁿ的二元序列线性复杂度和k-错线性复杂度之间的关系，给出了k-错线性复杂度严格小于线性复杂度的一个充分必要条件，给出了使得LC(S+E)＜LC(S)成立的用错误多项式E^N(x)表达的一个充分条件，给出了使得LC_k(S)＜LC(S)成立的最小的k值(即最小错误minerror(S))的一个上界，这里p为奇素数，z是模p的本原根．

The linear complexity and the k-error linear complexity of pn-periodic binary sequences

Not only should cryptographically strong sequences have a large linear complexity, but also the change of a few terms should not cause a significant decrease in linear complexity. This requirement leads to the concept of the k-error linear complexity of periodic sequences. A relationship between the linear complexity and the k-error linear complexity of p~n-periodic sequences over GF(2) is studied, where p is an odd prime, and z is a primitive root modular p~2. A necessary and sufficient condition that the k-error linear complexity be strictly less than the linear complexity is shown. A sufficient condition expressed by the error polynomial E~N(x) that (LC(S )(E)<)LC(S) and an upper bound of the minimum value k for which (LC_k(S)<)LC(S), i.e. minerror(S), are given.