Title: Autocorrelation and Lower Bound on the 2-Adic Complexity of LSB Sequence of $p$-ary $m$-Sequence,
Abstract: 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 input of the algorithm. Therefore, analyzing
their statistical property (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 $p^n-1$ for any positive $n\geq2$ to the problem of
determining autocorrelations of LSB sequence of period $p-1$. Then, based on
this property and computer calculation, we list some autocorrelation
distributions of LSB sequences of $p$-ary $m$-sequences with order $n$ for some
small primes $p$'s, such as $p=3,5,7,11,17,31$. Additionally, using their
autocorrelation distributions and the method inspired by Hu, we give the lower
bounds on the 2-adic complexities of these LSB sequences. Our results show that
the main parts of all the lower bounds on the 2-adic complexity of these LSB
sequencesare larger than $\frac{N}{2}$, where $N$ is the period of these
sequences. Therefor, 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=2^k-1$, since all its
bit-component sequences of a $p$-ary $m$-sequence are shift equivalent, our
results hold for all its bit-component sequences.