Autocorrelations of Maximum Period FCSR Sequences
Hong Xu, Wen‐Feng Qi · SIAM Journal on Discrete Mathematics · 2006
Let $\underline{a}$ be a maximum period feedback with carry shift register sequence (l‐sequence) with connection integer $q=p^e$ and period $T=p^{e-1}(p-1)$. It is shown that the expected value of its autocorrelations is 0, and its variance is $O(q\ln^{4}q)$. Thus when q is sufficiently large, with high probability, the autocorrelations are low. Furthermore, it is shown that when $e\geq2$, for any integer i, $1\leq i\leq e/2$, when the shift is a multiple of $T/2p^i$, the absolute value of the autocorrelations of $\underline{a}$ is $T/p^{2i-1}$, and the sign relies on the parity of the multiple.