On the linear complexity of Sidel'nikov sequences over nonprime fields (Q958251)

The authors introduce a generalization of Sidel'nikov sequences over arbitrary fields \(\mathbb F_{p^t}\). Let \(d=p^t\) divide \(q-1\) for a prime power \(q\). The cyclotomic classes of order \(d\) in \(\mathbb F_q\) are: \[ \begin{aligned} D_0 &= \{ \alpha^{dn}: 0\leq n\leq (q-1)/d -1\}\\ D_j &= \alpha^jD_0,\qquad 1\leq j\leq d-1, \end{aligned} \] for a primitive element \(\alpha\) of \(\mathbb F_q\). The sequence \(S: s_0,s_1, \dots\) is given by: \[ \begin{cases} s_n = j_0\beta_0+j_1\beta_1+\cdots +j_{t-1}\beta_{t-1}&\text{if \(\alpha^n+1\in D_j, n\neq (q-1)/2\)}\\ s_n = 0&\text{if \(n=(q-1)/2\)}\\ s_{n+q-1} = s_n&\text{if \(n >0\)}, \end{cases} \] where \((j_0,j_1, \dots , j_{t-1})\) is the \(p\)-adic representation of \(j\) and \(B=\{ \beta_0, \beta_1, \ldots , \beta_{t-1}\}\) is a basis of \(\mathbb F_{p^t}\) over \(\mathbb F_p\). The case \(t=1\) is the original sequence of \textit{V. M. Sidel'nikov} [Probl. Peredachi Inf. 5, No. 1, 16--22 (1969; Zbl 0295.94032)]. Assuming there is a one trace-one basis \(B\) and with various restrictions on \(q\), the authors give a lower bound on the linear complexity of \(S\), showing it to be large. They compute the exact linear complexity when \(d=8\). The primary tool is Weil's bound on character sums.