On the linear complexity of Sidel'nikov sequences over nonprime fields
type: Item
instance of: scholarly article
title: On the linear complexity of Sidel'nikov sequences over nonprime fields
zbMATH Open document ID: 1153.11060
author: Nina Brandstätter
author: Wilfried Meidl
published in: Journal of Complexity
publication date: 2008-12-03T00:00:00Z
review text: The authors introduce a generalization of Sidel'nikov sequences over arbitrary fields \(\mathbb F_{p^t}\). Let \(d=p^t\) divide \(q-1\) for a prime power \(q\). The cyclotomic classes of order \(d\) in \(\mathbb F_q\) are: \[ \begin{aligned} D_0 &= \{ \alpha^{dn}: 0\leq n\leq (q-1)/d -1\}\\ D_j &= \alpha^jD_0,\qquad 1\leq j\leq d-1, \end{aligned} \] for a primitive element \(\alpha\) of \(\mathbb F_q\). The sequence \(S: s_0,s_1, \dots\) is given by: \[ \begin{cases} s_n = j_0\beta_0+j_1\beta_1+\cdots +j_{t-1}\beta_{t-1}&\text{if \(\alpha^n+1\in D_j, n\neq (q-1)/2\)}\\ s_n = 0&\text{if \(n=(q-1)/2\)}\\ s_{n+q-1} = s_n&\text{if \(n >0\)}, \end{cases} \] where \((j_0,j_1, \dots , j_{t-1})\) is the \(p\)-adic representation of \(j\) and \(B=\{ \beta_0, \beta_1, \ldots , \beta_{t-1}\}\) is a basis of \(\mathbb F_{p^t}\) over \(\mathbb F_p\). The case \(t=1\) is the original sequence of \textit{V. M. Sidel'nikov} [Probl. Peredachi Inf. 5, No. 1, 16--22 (1969; Zbl 0295.94032)]. Assuming there is a one trace-one basis \(B\) and with various restrictions on \(q\), the authors give a lower bound on the linear complexity of \(S\), showing it to be large. They compute the exact linear complexity when \(d=8\). The primary tool is Weil's bound on character sums.
Mathematics Subject Classification ID: 11T71
Mathematics Subject Classification ID: 11T24
zbMATH DE Number: 5377203
zbMATH Keywords: Sidel'nikov sequence
zbMATH Keywords: linear complexity
zbMATH Keywords: cyclotomic classes
MaRDI profile type: Publication
full work available at URL: j.jco.2008.04.002
OpenAlex ID: W2157820864
cites work: On the number of trace-one elements in polynomial bases for \({\mathbb F}_{2^n}\)
cites work: On the Linear Complexity and $k$-Error Linear Complexity Over $ {\BBF }_{p}$ of the $d$-ary Sidel'nikov Sequence
cites work: Q4382830
cites work: On the Linear Complexity of Sidel’nikov Sequences over ${\mathbb {F}}_d$
cites work: Bounds on the Linear Complexity and the 1-Error Linear Complexity over F p of M-ary Sidel’nikov Sequences
cites work: Q4208589
cites work: One-Error Linear Complexity over F p of Sidelnikov Sequences
cites work: On the lower bound of the linear complexity over F/sub p/ of Sidelnikov sequences
cites work: Q4377092
cites work: Linear complexity over F/sub P/ and trace representation of Lempel-Cohn-Eastman sequences
cites work: Linear Complexity Over&lt;tex&gt;$F_p$&lt;/tex&gt;of Sidel'nikov Sequences
cites work: Q4421634
cites work: On the linear complexity of the Sidelnikov-Lempel-Cohn-Eastman sequences
cites work: A class of balanced binary sequences with optimal autocorrelation properties
cites work: Q3216750
cites work: Some notes on the linear complexity of Sidel'nikov-Lempel-Cohn-Eastman sequences
cites work: Q4330647
cites work: Progress in Cryptology - INDOCRYPT 2003
cites work: Linear Complexity and Random Sequences
cites work: Q4004196
cites work: Q4048942
cites work: Q5538955
DOI: 10.1016/J.JCO.2008.04.002
Recommended article: Addendum to Sidel'nikov sequences over nonprime fields
Recommended article: Linear Complexity Over&lt;tex&gt;$F_p$&lt;/tex&gt;of Sidel'nikov Sequences
Recommended article: One-Error Linear Complexity over F p of Sidelnikov Sequences
Recommended article: On the Linear Complexity of Sidel’nikov Sequences over ${\mathbb {F}}_d$
Recommended article: On the k-error Linear Complexity of Subsequences of d-ary Sidel’nikov Sequences Over Prime Field 𝔽d
Recommended article: On the lower bound of the linear complexity over F/sub p/ of Sidelnikov sequences
Recommended article: Linear Complexity over F p of Ternary Sidel’nikov Sequences
Recommended article: On the Linear Complexity and $k$-Error Linear Complexity Over $ {\BBF }_{p}$ of the $d$-ary Sidel'nikov Sequence
Recommended article: 𝑘-error linear complexity over 𝔽 p of subsequences of Sidelnikov sequences of period (pr – 1)/3
Recommended article: Q3635535
description: scientific article; zbMATH DE number 5377203