Pseudorandom sequences constructed by the power generator (Q2466314)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Pseudorandom sequences constructed by the power generator |
scientific article |
Statements
Pseudorandom sequences constructed by the power generator (English)
0 references
14 January 2008
0 references
For a binary sequence \(E_N=(e_1,\dots,e_N)\in \{-1,+1\}^N\) the following pseudorandomness measures were introduced by \textit{C. Mauduit} and \textit{A. Sárközy} [Acta Arith., 82, 365--377 (1997; Zbl 0886.11048)]: \(\bullet\) the well-distribution measure \[ W(E_N)=\max_{a,b,t} \left| \sum_{j=1}^t e_{a+jb}\right| , \] where the maximum is taken over all integers \(a\) and \(b,t>0\) such that \(1\leq a+b\leq a+bt\leq N\). \(\bullet\) the correlation measure of order \(l\) \[ C_l(E_N)=\max_{M,D}\left| \sum_{n=1}^M e_{n+d_1}\cdots e_{n+d_l}\right| , \] where the maximum is taken over all \(D=(d_1,\dots,d_l)\) and \(M\) such that \(0\leq d_1<\dots<d_l<M+d_l\leq N\); \(\bullet\) the normality measure of order \(l\) \[ N_l(E_N)=\max_{M,X}\left| \left| \{0\leq n<M : (e_{n+1},e_{n+2},\dots,e_{n+l})=X\}\right| -\frac{M}{2^l}\right| , \] where the maximum is taken over all \(X=(x_1,\dots,x_l)\in \{-1,+1\}^l\), and \(M\) such that \(0<M\leq N-l+1.\) For integers \(k\geq 2\), \(m\geq 1\) and \(\vartheta\) such that \(\gcd(\vartheta,m)=1\), the power generator is the sequence \((u_n)\) defined by \[ u_n\equiv u_{n-1}^k \bmod m,\quad 0\leq u_n<m,\quad n\geq 1, \] with some initial value \(u_0=\vartheta\). For the case that \(m=p>2\) is a prime the author derives binary sequences from \((u_n)\) either by \(e_n=1\) if \(u_n\) is even and \(e_n=-1\) if \(u_n\) is odd or by \(e_n=1\) if \(0\leq u_n<p/2\) and \(e_n=-1\) if \(p/2<u_n<p\). For these binary sequences she proves bounds on the above measures of pseudorandomness. The proofs are based on bounds on exponential sums.
0 references
pseudorandomness
0 references
binary sequences
0 references
well-distribution measure
0 references
correlation measure
0 references
normality measure
0 references
power generator
0 references
Blum-Blum-Shub generator
0 references