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

DOI10.1155/2019/8635209MaRDI QIDQ2325205zbMATH OpenOpenAlexFDO

Publication date 9 September 2019

Published in Complexity (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1901.10086

Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Analysis of algorithms and problem complexity (68Q25) Shift register sequences and sequences over finite alphabets in information and communication theory (94A55) Cryptography (94A60)

Abstract: Let

q = p^{r}

be a power of an odd prime

p

. We study binary sequences

s i g m a = (s i g m a_{0}, s i g m a_{1}, l d o t s)

with entries in

0, 1

defined by using the quadratic character

c h i

of the finite field

m a t h b b F_{q}

:

sigma_n=left{ �egin{array}{ll} 0,& mathrm{if}quad n= 0,\ (1-chi(xi_n))/2,&mathrm{if}quad 1leq n< q, end{array} ight.

for the ordered elements

x i_{0}, x i_{1}, l d o t s, x i_{q - 1} i n m a t h b b F_{q}

. The

s i g m a

is Legendre sequence if

r = 1

. Our first contribution is to prove a lower bound on the linear complexity of

s i g m a

for

r g e q 2

. The bound improves some results of Meidl and Winterhof. Our second contribution is to study the

k

-error linear complexity of

s i g m a

for

r = 2

. It seems that we cannot settle the case when

r > 2

and leave it open.

Review text

Summary: Let \(\mathbb{F}_q\) be the finite field with \(q = p^r\) elements, where \(p\) is an odd prime. For the ordered elements \(\xi_0, \xi_1, \dots, \xi_{q - 1} \in \mathbb{F}_q\), the binary sequence \(\sigma = (\sigma_0, \sigma_1, \dots, \sigma_{q - 1})\) with period \(q\) is defined over the finite field \(\mathbb{F}_2 = \{0,1 \}\) as follows: \(\sigma_n= \{ 0,\text{ if } n=0, (1-\chi (\xi_n))/ 2, \text{ if }1\leq n< q\}\), \(\sigma_{n+q}=\sigma_n\) where \(\chi\) is the quadratic character of \(\mathbb{F}_q\). Obviously, \(\sigma\) is the Legendre sequence if \(r = 1\). In this paper, our first contribution is to prove a lower bound on the linear complexity of \(\sigma\) for \(r \geq 2\), which improves some results of \textit{W. Meidl} and \textit{A. Winterhof} [IEEE Trans. Inf. Theory 47, No. 7, 2807--2811 (2001; Zbl 1032.94004)]. Our second contribution is to study the distribution of the \(k\)-error linear complexity of \(\sigma\) for \(r = 2\). Unfortunately, the method presented in this paper seems not suitable for the case \(r > 2\) and we leave it open.

Recommendations

Cites work

Cited in

(5)

This page was built for publication: On the \(k\)-error linear complexity of binary sequences derived from the discrete logarithm in finite fields

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2325205)