On the $k$-error linear complexity of binary sequences derived from the discrete logarithm in finite fields
This work addresses a theoretical problem in cryptography and coding theory, focusing on sequence properties for security applications, but it is incremental as it builds on existing methods and leaves open cases for r > 2.
The paper tackles the problem of analyzing the linear complexity and k-error linear complexity of binary sequences derived from the discrete logarithm in finite fields, proving a lower bound for r ≥ 2 and studying specific cases for r = 2, with results improving upon prior work by Meidl and Winterhof.
Let $q=p^r$ be a power of an odd prime $p$. We study binary sequences $σ=(σ_0,σ_1,\ldots)$ with entries in $\{0,1\}$ defined by using the quadratic character $χ$ of the finite field $\mathbb{F}_q$: $$ σ_n=\left\{ \begin{array}{ll} 0,& \mathrm{if}\quad n= 0,\\ (1-χ(ξ_n))/2,&\mathrm{if}\quad 1\leq n< q, \end{array} \right. $$ for the ordered elements $ξ_0,ξ_1,\ldots,ξ_{q-1}\in \mathbb{F}_q$. The $σ$ is Legendre sequence if $r=1$. Our first contribution is to prove a lower bound on the linear complexity of $σ$ for $r\geq 2$. The bound improves some results of Meidl and Winterhof. Our second contribution is to study the $k$-error linear complexity of $σ$ for $r=2$. It seems that we cannot settle the case when $r>2$ and leave it open.