On the \(k\)-error linear complexity of binary sequences derived from the discrete logarithm in finite fields (Q2325205)

Summary: Let \(\mathbb{F}_q\) be the finite field with \(q = p^r\) elements, where \(p\) is an odd prime. For the ordered elements \(\xi_0, \xi_1, \dots, \xi_{q - 1} \in \mathbb{F}_q\), the binary sequence \(\sigma = (\sigma_0, \sigma_1, \dots, \sigma_{q - 1})\) with period \(q\) is defined over the finite field \(\mathbb{F}_2 = \{0,1 \}\) as follows: \(\sigma_n= \{ 0,\text{ if } n=0, (1-\chi (\xi_n))/ 2, \text{ if }1\leq n< q\}\), \(\sigma_{n+q}=\sigma_n\) where \(\chi\) is the quadratic character of \(\mathbb{F}_q\). Obviously, \(\sigma\) is the Legendre sequence if \(r = 1\). In this paper, our first contribution is to prove a lower bound on the linear complexity of \(\sigma\) for \(r \geq 2\), which improves some results of \textit{W. Meidl} and \textit{A. Winterhof} [IEEE Trans. Inf. Theory 47, No. 7, 2807--2811 (2001; Zbl 1032.94004)]. Our second contribution is to study the distribution of the \(k\)-error linear complexity of \(\sigma\) for \(r = 2\). Unfortunately, the method presented in this paper seems not suitable for the case \(r > 2\) and we leave it open.