Construction of pseudorandom binary sequences by using the multiplicative inverse (Q2568523): Difference between revisions

In the paper the authors investigate pseudorandom properties of families of binary sequences based on the use of multiplicative inverses modulo a prime \(p\). Let \(f(x)\in F_p[x]\) be a polynomial of degree \(k\) with \(0<k<p\) and with no multiple zeros in the algebraic closure of \(F_p\). The binary sequence \(E_p=\{e_1,\dots,e_p\}\) defined by \(e_n=+1\) if \((f(n),p)=1\) and the least non-negative residue of \(f(n)\) modulo \(p\) is \(<p/2\), and \(e_n=-1\) otherwise. Then for the well-distribution measure \(W(E_p):=\max|\sum_{j=0}^{t-1}e_{a+jb}|\) they prove \(W(E_p)\ll kp^{1/2}(\log p)^2\). Let \(\ell\in{bf N}\), \(2\leq\ell\leq p\). Provided \(e=2\) or \((4k)^\ell <p\), then for the correlation measure \(C_\ell(E_p):=\max|\sum_{n=1}^M e_{n+d_1}e_{n+d_2}\dots e_{n+d_\ell}|\) of order \(\ell\), where \(D=(d_1,\dots,d_\ell)\), \(0\leq d_1<\dots<d_\ell\leq N-M\), they proved \(C_\ell(E_p)\ll k\ell p^{1/2}(\log p)^{\ell+1}\). The last result is also true under the conditions \(k\ell<p/2\) and \(f(x)=(x+a_1)\dots(x+a_k)\), \(a_1,\dots,a_k\in F_p\), \(a_i\neq a_j\) for \(i\neq j\).