On the linear complexity of the Sidelnikov-Lempel-Cohn-Eastman sequences (Q1404324)

Let \(q\) be an odd prime power, \(\alpha\) be a primitive element of \(\mathbb F_q\), and \(\eta\) denote the quadratic character of \(\mathbb F_q\). Then the Sidelnikov-Lempel-Cohn-Eastman sequence is defined to be the \((q-1)\)-periodic binary sequence \(s_q = s_0, s_1 \ldots\) with \[ s_j = \begin{cases} 1 & \text{if}\;\eta(\alpha^j+1) = -1, \\ 0 & \text{otherwise}, \end{cases}\quad j=0,1,\ldots. \] The linear complexity of \(s_q\), i.e. the length of the shortest linear recurrence relation \(-s_j = c_1s_{j-1}+\ldots+c_ls_{j-l}\), \(j \geq l\), over \(\mathbb F_2\) satisfied by \(s_q\), equals the degree of the feedback polynomial \(c(x) = 1+c_1x+\ldots+c_lx^l\). The feedback polynomial is also given by \[ c(x) = \frac{x^{q-1}+1}{\gcd(x^{q-1}+1,S_q(x))}, \;\text{where}\; S_q(x) = s_0+s_1x+\ldots+s_{q-2}x^{q-2}. \] Firstly the authors derive conditions for \(q\) under which \((x+1)^i, i = 1,2\), divides respectively under which \((x+1)^4\) does not divide \(\gcd(x^{q-1}+1,S_q(x))\). Secondly, for \(q = df+1\), \(d\) odd, conditions under which \(\gcd(x^{q-1}+1,S_q(x))\) is divisible by \(x^{d-1}+x^{d-2}+\ldots+1\) are presented. These conditions are given in terms of Jacobsthal sums. Using these results several statements on the feedback polynomial and on the linear complexity of \(s_q\) can be found. In particular for the case that \(q = 2^kr+1\) and \(2\) is a primitive root modulo \(r\) (then \(x^{q-1}+1 = ((x+1)(x^{r-1}+x^{r-2}+\ldots+1))^{2^k}\) is the canonical factorization) it has been shown that \(c(x) = (x^{q-1}+1)/(x+1)\) if \(k = 2\), and that \(c(x) = (x^{q-1}+1)/(x+1)^i\) for some \(i \geq 2\) if \(k \geq 3\) and \(r\) is sufficiently large. (The case \(k=1\) has already been solved by\textit{T. Helleseth} and \textit{K. Yang} [Proc. SETA`01, 209--217 (2002; Zbl 1030.94027)].)