一类LFSR序列簇的2-adic复杂度

THE 2-ADIC COMPLEXITY OF A CLASS OF LFSR SEQUENCE FAMILIES

线性复杂度和2-adic复杂度是衡量序列伪随机性的两个重要指标.文章研究这两个指标之间的关系,证明了由不可约多项式生成的LFSR序列簇的极小连接数达到最大可能值,即2~T-1,其中T为不可约多项式的周期,进而该序列簇的2-adic复杂度与对称2-adic复杂度均达到最大可能取值.特别地,当限定不可约多项式是本原多项式时,即可得到m-序列的相应结论.

Linear complexity and 2-adic complexity are two important measures of the pseudorandomness of sequences.In this paper,the relationship between these two measures is considered.The LFSR sequence family generated by an irreducible polynomial is set as the main object of this paper.As the LFSR sequence family is formed with all zero sequence and s shift equivalence classes of sequences of which the minimal connection integers are equal,where s is related to the degree n and period T of the corresponding irreducible polynomial by s =（2~n-1）/T,the least common multiple of the s minimal connection integers is defined as the minimal connection integer of the LFSR sequence family.Then the 2-adic complexity and symmetric2-adic complexity of the LFSR sequence family are properly defined.It is shown that the minimal connection integer of the LFSR sequence family generated by an irreducible polynomial attains the maximum,that is 2~T- 1,where T is the period of the corresponding irreducible polynomial,and so do the 2-adic complexity and symmetric 2-adic complexity.In particular,the conclusion that the 2-adic complexity of a binary m-sequence attains the maximum can also be obtained,when the irreducible polynomial is further restricted to a primitive polynomial.