Multiplicative character sums of Fermat quotients and pseudorandom sequences
type: Item
instance of: scholarly article
title: Multiplicative character sums of Fermat quotients and pseudorandom sequences
zbMATH Open document ID: 1263.11110
author: Domingo Gomez
author: Arne Winterhof
published in: Periodica Mathematica Hungarica
publication date: 2012-09-17T00:00:00Z
review text: 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.
reviewed by: Florian Luca
Mathematics Subject Classification ID: 11T24
Mathematics Subject Classification ID: 11K45
Mathematics Subject Classification ID: 11K36
Mathematics Subject Classification ID: 11T71
Mathematics Subject Classification ID: 94A55
zbMATH DE Number: 6083225
zbMATH Keywords: Fermat quotients
zbMATH Keywords: finite fields
zbMATH Keywords: character sums
zbMATH Keywords: pseudorandom sequences
zbMATH Keywords: discrete logarithm
zbMATH Keywords: correlation measure
zbMATH Keywords: linear complexity
MaRDI profile type: Publication
full work available at URL: s10998-012-3747-1
OpenAlex ID: W2132474171
cites work: Boolean functions derived from Fermat quotients
cites work: Linear complexity profile of binary sequences with small correlation measure
cites work: Structure of Pseudorandom Numbers Derived from Fermat Quotients
cites work: Linear complexity profile of \(m\)-ary pseudorandom sequences with small correlation measure
cites work: On the distribution of pseudorandom numbers and vectors derived from Euler-Fermat quotients
cites work: On the 𝑝-divisibility of Fermat quotients
cites work: Q4885320
cites work: Q4830109
cites work: On finite pseudorandom binary sequences I: Measure of pseudorandomness, the Legendre symbol
cites work: On finite pseudorandom sequences of \(k\) symbols.
cites work: Progress in Cryptology - INDOCRYPT 2003
cites work: Pseudorandomness and Dynamics of Fermat Quotients
cites work: Cryptographic applications of analytic number theory. Complexity lower bounds and pseudo\-randomness
cites work: CHARACTER SUMS WITH FERMAT QUOTIENTS
cites work: Q3062108
DOI: 10.1007/S10998-012-3747-1
description: scientific article; zbMATH DE number 6083225