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

2019/01/29 by Chen, Zhixiong, Wang, Qiuyan
#96A60 #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #FOS: Mathematics #Number Theory (math.NT)

paper · doi:10.48550/arxiv.1901.10086

Abstract

Let q=p^r be a power of an odd prime p. We study binary sequences σ=(σ₀,σ₁,…) with entries in \0,1\ defined by using the quadratic character χ of the finite field \mathbbF_q: σ_n=\ 0, · amp; if n= 0,
(1-χ(ξ_n))/2, · amp;if 1≤ n · lt; q, . for the ordered elements ξ₀,ξ₁,…,ξ_q-1∈ \mathbbF_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.

Related

• On k-error linear complexity of binary sequences derived from Euler quotients modulo 2p
• Improved lower bound on the family complexity of Legendre sequences
• Efficient Algorithm for the Linear Complexity of Sequences and Some\n Related Consequences
• Periodic sequences with stable k-error linear complexity
• An Algorithm for Computing m-Tight Error Linear Complexity of Sequences over GF(p^m) with Period p^m