Multiplicative character sums of Fermat quotients and pseudorandom sequences (Q452834): Difference between revisions

For a prime \(p\) and integer \(u\) coprime to \(p\) let \(q_p(u)=(u^{p-1}-1)/p\pmod p\) be the so-called Fermat quotient modulo \(p\). Set also \(q_p(u)=0\) if \(p\mid u\). In the paper under review, the authors give a bound on sums of products of multiplicative characters of shifted Fermat quotients modulo \(p\). The exact statement and result is that the bound \[ \sum_{u=0}^{N-1} \psi_1(q_p(u+d_1))\psi_2(q_p(u+d_2))\cdots \psi_{\ell}(q_p(u+d_{\ell}))\ll \max\{\ell N p^{-1/3}, \ell p^{3/2} \log p\} \] holds when \(\psi_1,\ldots,\psi_{\ell}\) are nontrivial characters modulo \(p\), \(0<d_1<\ldots<d_{\ell}\leq p^2-1\) are integers and \(1\leq N\leq p^2\) is also an integer. The proof uses the Weil bounds. As applications, the authors derive bounds the pseudorandomness of the sequences of modular discrete logarithms of Fermat quotients modulo \(p\). These are the sequences \((e_u)_{u}\) given by \(\chi(q_p(u))=\exp(2\pi i e_u/m)\) (\(0\leq e_u<m\)) if \(q_p(u)\not\equiv 0\pmod p\) and \(e_u=0\) otherwise, where \(\chi\) is a fixed multiplicative character modulo \(p\) of order \(m\). In particular, the authors deduce upper bounds for the \(f\)-well-distribution measure and \(f\)-correlation measure of order \(\ell\) of the sequences \((e_u)_u\), as well as a lower bound on their linear complexity.