On linear recursion and pseudorandomness
For a finite binary sequence \(e_1, \ldots, e_N\) of length \(N\) and terms \(e_i \in \{-1,+1\}\), \textit{C. Mauduit} and \textit{A. Sarközy} [Acta Arith. 82, 365--377 (1997; Zbl 0886.11048)] suggested the pseudorandomness measures \(U(E_N,t,a,b) = \sum_{j=1}^te_{a+jb}\) and \(W(E_N) = \max_{a,b,t}| U(E_N,t,a,b)| \), \(1 \leq a+b \leq a+tb \leq N\), (well-distribution), as well as the measures \(V(E_N,M,D) = \sum_{n=1}^M\prod_{r=1}^le_{n+d_r}\) for \(D = (d_1,\ldots,d_l)\) with nonnegative integers \(0 \leq d_1 < \cdots < d_l\) and \(M+d_l \leq N\), and \(C_l(E_N) = \max_{M,D}| V(E_N,M,D)| \) (correlation). If \(l= 0\) and \(D = (0,d)\) then \(V(E_N,M,D)\) is the conventional autocorrelation of a finite sequence. Let \(\mathbb F_p\) be the prime field with \(p\) elements, \(\lambda \in \mathbb F_p\setminus\{0\}\) an element with multiplicative order \(T\) modulo \(p\), and \(f(x) \in \mathbb F_p[x]\) a polynomial of degree \(k\). The authors define sequences over \(\{-1,+1\}\) of period \(T\) by \[ e_n = \begin{cases} l \text{ if }l \left(\frac{f(\lambda^n)}{p}\right) & p \nmid f(\lambda^n), \\ 1 & p\mid f(\lambda^n), \end{cases} \] where \((\frac{a}{p})\) denotes the Legendre symbol, and consider the finite part of length \(T\) given by a period. As main results they show that these finite binary sequences satisfy \(W(E_T) < 5kp^{1/2}\log p\) provided that \(f(x)\) is not of the form \(cx^\alpha(g(x))^2\), and specify sufficient conditions on \(f(x)\) and \(l\) such that \(C_l(E_T) \leq 5klp^{1/2}\log p\). The sequences considered in this paper can be seen as generalizations of the binary Sidelnikov sequence where \(f(x) = x+1\) and \(\lambda\) is a primitive element of \(\mathbb F_p\). The periodic autocorrelation of this sequence has been proved to be two-valued and best possible by \textit{A. Lempel} et \textit{al.} [IEEE Trans. Inf. Theory 23, 38--42 (1977; Zbl 0359.94018)]. The complete periodic autocorrelation spectrum of its generalization to an \(m\)-ary sequence is presented in \textit{Y.-S. Kim} et al. [IEEE Trans. Inf. Theory 51, 3303--3307 (2005)].
- Pseudorandomness of binary sequences derived from linear recursions
- On a family of pseudorandom binary sequences
- On finite pseudorandom binary sequences I: Measure of pseudorandomness, the Legendre symbol
- On pseudorandom binary sequences constructed by using finite fields
- Measures of pseudorandomness for binary sequences constructed using finite fields
- Construction of pseudorandom binary sequences using additive characters over \(GF(2^k)\)
- Concatenation of pseudorandom binary sequences
- Linear complexity profile of binary sequences with small correlation measure
- On a family of pseudorandom binary sequences
- On the d-ary generalized Legendre-Sidelnikov sequence
- Pseudorandomness of binary sequences derived from linear recursions
- Pseudorandomness for Linear Length Branching Programs and Stack Machines
- Multiplicative character sums of a class of nonlinear recurrence vector sequences
- scientific article; zbMATH DE number 5619271 (Why is no real title available?)
- Random number generators based on linear recurrences in \(\mathbb{F}_{2^w}\)
- Elliptic curve analogues of a pseudorandom generator
- Measures of pseudorandomness: arithmetic autocorrelation and correlation measure
- New sequences of period \(p^n\) and \(p^n+1\) via projective linear groups
- Large Families of Pseudorandom Sequences of k Symbols and Their Complexity – Part I
- On Pseudorandom Sequences and Their Application
- On the pseudorandom properties of k-ary Sidel'nikov sequences
- Linear recursion properties of uncorrelated binary sequences
- A technique to study the correlation measures of binary sequences
This page was built for publication: On linear recursion and pseudorandomness
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5315177)
