Autocorrelation and Lower Bound on the 2-Adic Complexity of LSB Sequence of p-ary m-Sequence
In modern stream cipher, there are many algorithms, such as ZUC, LTE encryption algorithm and LTE integrity algorithm, using bit-component sequences of p-ary m-sequences as the inputs of the algorithms.Therefore, analyzing the statistical properties (For example, autocorrelation, linear complexity and 2-adic complexity) of bit-component sequences of p-ary m-sequences is becoming an important research topic.In this paper, we first derive some autocorrelation properties of LSB (Least Significant Bit) sequences of p-ary m-sequences, i.e., we convert the problem of computing autocorrelations of LSB sequences of period pn-1 for any positive n ≥ 2 to the problem of determining autocorrelations of LSB sequences of period p-1.Then we give explicit formula of the autocorrelation distributions of the LSB sequences of p-ary m-sequences with order n ≥ 2 for p < 100.Additionally, taking p =3, 7 as two representatives of Mersenne primes, p =5, 13 as two representatives of primes p 1 mod 4 and p =11, 19 as two representatives of primes p 3 mod 4, we analyze the 2-adic complexities of the LSB sequences of p-ary m-sequences give lower bounds on the 2-adic complexities of these sequences.Our results show that the main parts of all the lower bounds on the 2-adic complexities of these LSB sequences are larger than N/2, where N is the period of these sequences.Therefore, these bounds are large enough to resist the analysis of RAA (Rational Approximation Algorithm) for FCSR (Feedback with Carry Shift Register).Especially,for a Mersenne prime p =2k-1 (i.e., k is a prime such that p is also a prime), since all its bit-component sequences of a p-ary m-sequence are shift equivalent, our results hold for all its bit-component sequences.
p-ary m-sequence LSB sequence autocorrelation 2-adic complexity
Yuhua Sun Qiang Wang Tongjiang Yan Chune Zhao
College of Sciences, China University of Petroleum,Qingdao 266555, Shandong, China;School of Mathema School of Mathematics and Statistics, Carleton University, Ottawa,Ontario,K1S 5B6, Canada College of Sciences, China University of Petroleum,Qingdao 266555, Shandong, China;Qilu University o College of Sciences, China University of Petroleum,Qingdao 266555, Shandong, China
国际会议
广州
英文
87-106
2018-05-01（万方平台首次上网日期，不代表论文的发表时间）