On the k-error linear complexity of binary sequences derived from the discrete logarithm in finite fields
share
Let q=p^r be a power of an odd prime p. We study binary sequences σ=(σ_0,σ_1,...) with entries in {0,1} defined by using the quadratic character χ of the finite field F_q: σ_n={< a r r a y >. for the ordered elements ξ_0,ξ_1,...,ξ_q-1∈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≥ 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.
READ FULL TEXT