On the k-Error Linear Complexity of Binary Sequences Derived from the Discrete Logarithm in Finite Fields

Abstract EN

Let Fq be the finite field with q=pr elements, where p is an odd prime.

For the ordered elements ξ0,ξ1,…,ξq-1∈Fq, the binary sequence σ=(σ0,σ1,…,σq-1) with period q is defined over the finite field F2={0,1} as follows: σn=0, if n=0, (1-χ(ξn))/2, if 1≤n

Obviously, σ is the Legendre sequence if r=1.

In this paper, our first contribution is to prove a lower bound on the linear complexity of σ for r≥2, which improves some results of Meidl and Winterhof.

Our second contribution is to study the distribution of the k-error linear complexity of σ for r=2.

Unfortunately, the method presented in this paper seems not suitable for the case r>2 and we leave it open.