×

Bounds for exponential sums and their applications to pseudorandom numbers. (English) Zbl 0957.11050

Authors’ introduction: Let \(F_q\) be the finite field of order \(q\), where \(q\) is an arbitrary prime power, and let \(F^*_q\) denote the set of nonzero elements of \(F_q\). We define \(\overline c=c^{-1}\in F^*_q\) for \(c\in F^*_q\) and \(\overline c=0\in F_q\) for \(c=0\in F_q\). If \(q\geq 3\), then we may equivalently put \(\overline c=c^{q-2}\) for \(c\in F_q\). We are primarily interested in complete exponential sums of the form \[ E(\chi; {\mathbf d}, {\mathbf e}):= \sum_{n\in F_q} \chi\left(\sum^s_{j=1} d_j\overline {n+e_j} \right), \] where \(s\) is a positive integer, \(\chi\) is a nontrivial additive character of \(F_q\), and \({\mathbf d}= (d_1,\dots, d_s)\in F^s_q\) and \({\mathbf e}=(e_1, \dots, e_s) \in F_q^s\) are \(s\)-tuple of elements of \(F_q\) on which we will occasionally place minor restrictions to avoid trivial cases. For \(q=p\) a prime, we will also consider the corresponding incomplete exponential sums \[ E_N(\chi; {\mathbf d}, {\mathbf e}): =\sum^{N-1}_{n=0} \chi\left(\sum^s_{j=1} d_j\overline {n+e_j} \right) \quad\text{for }1\leq N\leq p. \] These exponential sums arise, for instance, in the analysis of a new method for pseudorandom number generation, the so-called explicit inversive congruential method. We deduce an upper bound for the exponential sums \(E(\chi; {\mathbf d}, {\mathbf e})\) from the Bombieri-Weil bound. The corresponding incomplete exponential sums are treated in the wider context of exponential sums with rational functions in their arguments. The average values (in the mean-square sense) of the complete and incomplete exponential sums are calculated and lower bounds for the exponential sums are derived. The applications of the results to the analysis of pseudorandom numbers generated by the explicit inversive congruential method is presented.

MSC:

11T23 Exponential sums
11K45 Pseudo-random numbers; Monte Carlo methods
11L07 Estimates on exponential sums
PDFBibTeX XMLCite
Full Text: DOI EuDML