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

The linear complexity and the k-error linear complexity of p^n-periodic binary sequences

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

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.