Linear complexity profile of binary sequences with small correlation measure
The linear complexity profile \(L(s_n,N)\) of a sequence \((s_n), n=0,1\dots\) over the field \(\mathbb F_2\) is the function which for every integer \(N \geq 2\) is defined as the shortest length \(L\) of a recurrence relation over \(\mathbb F_2\) the first \(N\) terms of the sequence satisfy. For a \(T\)-periodic binary sequence \((s_n)\), \textit{C. Mauduit} and \textit{A. Sárközy} [Acta Arith. 82, 365--377 (1997; Zbl 0886.11048)] introduced the correlation measure \(C_k(s_n)\) of order \(k \geq 1\) defined by \[ C_k(s_n) = \max_{M,D}\left| \sum_{n=0}^{M-1}(-1)^{s_{n+d_1}+s_{n+d_2}+\cdots+s_{n+d_k}}\right| ,\tag{1} \] where the maximum is taken over all \(D = (d_1,d_2,\dots,d_k)\) with nonnegative integers \(d_1 < d_2 < \dots < d_k\) and \(M\) such that \(M-1+d_k \leq T-1\). The authors discover a relation between these two complexity measures, namely \[ L(s_n,N) \geq N - \max_{1\leq k\leq L(s_n,N)+1}C_k(s_n), \] for \(2 \leq N \leq T-1\) (Theorem 1). Then they apply this relation to known results on the pseudorandomness measure (1) to obtain results on the linear complexity profile of the discrete logarithm threshold sequence (cf. \textit{A. Sárközy} [Studia Sci. Math. Hung. 38, 377--384 (2001; Zbl 0997.11062)]), the Legendre sequence and the two-prime generator. Finally the authors estimate \(C_k(e_n)\) for the binary Sidel'nikov sequence \((e_n)\), and present the resulting estimation for \(L(e_n,N)\).
- Linear complexity profile of \(m\)-ary pseudorandom sequences with small correlation measure
- Correlation measure, linear complexity and maximum order complexity for families of binary sequences
- Linear complexity and related complexity measures
- scientific article; zbMATH DE number 5150220
- On the measures of pseudorandomness of binary sequences.
- Boolean functions derived from pseudorandom binary sequences
- Distribution of digital explicit inversive pseudorandom numbers and their binary threshold sequence
- Measures of pseudorandomness: arithmetic autocorrelation and correlation measure
- On linear recursion and pseudorandomness
- On finite pseudorandom sequences of k symbols.
- Modified constructions of binary sequences using multiplicative inverse
- Construction of pseudorandom binary sequences using additive characters over \(GF(2^k)\)
- On the \(N\)th linear complexity of automatic sequences
- Hamming correlation of higher order
- Perfect linear complexity profile and apwenian sequences
- Correlation measure, linear complexity and maximum order complexity for families of binary sequences
- \(r\)-th order nonlinearity, correlation measure and least significant bit of the discrete logarithm
- Improving results on the pseudorandomness of sequences generated via the additive order of a finite field
- On lattice profile of the elliptic curve linear congruential generators
- A family of elliptic curve pseudorandom binary sequences
- Boolean functions derived from pseudorandom binary sequences
- Linear complexity and related complexity measures
- On pseudorandom binary sequences constructed by using finite fields
- On the linear complexity of binary lattices
- On discrete Fourier transform, ambiguity, and Hamming-autocorrelation of pseudorandom sequences
- Multiplicative character sums of Fermat quotients and pseudorandom sequences
- Measures of pseudorandomness: arithmetic autocorrelation and correlation measure
- Minimum linear span approximation of binary sequences
- The Linear Complexity of Some Binary Sequences With Three-Level Autocorrelation
- On the pseudorandomness of binary and quaternary sequences linked by the Gray mapping
- On the Structure of Inversive Pseudorandom Number Generators
- Construction of pseudorandom binary sequences using additive characters over GF(2ᵏ). II
- Linear complexity profile of \(m\)-ary pseudorandom sequences with small correlation measure
- Some notes on the pseudorandomness of Legendre symbol and Liouville function
- Linear complexity profile and correlation measure of interleaved sequences
- A technique to study the correlation measures of binary sequences
This page was built for publication: Linear complexity profile of binary sequences with small correlation measure
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2466313)
