On the $k$-error linear complexity of binary sequences derived from the discrete logarithm in finite fields

Abstract

Let $q=p^r$ be a power of an odd prime $p$. We study binary sequences $\sigma =({\sigma }_0,{\sigma }_1,\dots )$ with entries in $\{0,1\}$ defined by using the quadratic character $\chi$ of the finite field ${\mathbb{F}}_q$: $${\sigma }_n=\{\begin{array}{ll}0,& \mathrm{if}n=0,\\ (1-\chi ({\xi }_n))/2,& \mathrm{if}1\le n<q,\end{array}$$ for the ordered elements ${\xi }_0,{\xi }_1,\dots ,{\xi }_{q-1}\in {\mathbb{F}}_q$. The $\sigma$ is Legendre sequence if $r=1$. Our first contribution is to prove a lower bound on the linear complexity of $\sigma$ for $r\ge 2$. The bound improves some results of Meidl and Winterhof. Our second contribution is to study the $k$-error linear complexity of $\sigma$ for $r=2$. It seems that we cannot settle the case when $r>2$ and leave it open.