Niederreiter, Harald; Winterhof, Arne Incomplete exponential sums over finite fields and their applications to new inversive pseudorandom number generators. (English) Zbl 0969.11040 Acta Arith. 93, No. 4, 387-399 (2000). Let \(\mathbb{F}_q\) be the finite field of order \(q=p^k\), where \(p\) is prime and \(k\in\mathbb{N}\), and let \(\{\beta_1,\dots, \beta_k\}\) be an ordered basis of \(\mathbb{F}_q\) over \(\mathbb{F}_p\). We construct an infinite period sequence \(\{ \xi_n\}^\infty_{n=0}\) by defining \(\xi_n=n_1 \beta_1+ \cdots+ n_k\beta_k\), if \(0 \leq n\leq q-1\) and \(n=n_1+ n_2p+\cdots+ n_kp^{k-1}\), \(0\leq n_i<p\); and \(\xi_{n+q} =\xi_n\) if \(n\geq 0\). For \(\alpha\in \mathbb{F}^*_q\) and \(\beta\in\mathbb{F}_q\) we generate a sequence \(\{\gamma_n\}^\infty_{n=0}\) by \(\gamma_n= \overline {\alpha\xi_n+ \beta}\), \(n=0,1,\dots,\) where \(\overline a-a^{-1}\) if \(a\neq 0\) and \(\overline 0= 0\). Furthermore we define \(n\oplus i\) \((n,i\in \mathbb{N}\cup \{0\})\) by \(n\oplus i= j\) iff \(\xi_n+ \xi_i=\xi_j\), \(0\leq j<q\).The authors give upper bounds for the exponential sum \[ S_N=\sum^{N-1}_{n=0} \chi\left( \sum^{s-1}_{i=0} \mu_i\nu_{n\oplus i}\right), \quad 1\leq N\leq q, \] where \(\mu_0,\dots, \mu_{s-1}\) are not all zero, and \(\chi\) is a nontrivial additive character of \(\mathbb{F}_q\), as follows:(i) \(|S_q|\leq(2s-2) q^{1/2}+s+1\); (ii) \(|S_N |< s(2q^{1/2} +1)(4\pi^{-2} \ell\log p+1.38 \ell+1)\) with \(\ell= \lceil(\log N)/ \log p\rceil\) \((1\leq N<q)\); (iii) \(|S_N|<\sqrt 5s^{1/2} N^{1/ 2} q^{1/4}+ q^{1/2}+1\) \((1\leq N<p)\).Using these bounds the authors obtain some nontrivial results on the distribution of sequences of digital explicit inversive pseudorandom numbers and explicit inversive pseudorandom vectors, which generalize or extend certain previous results [J. Eichenauer-Herrmann, Math. Comput. 60, 375-384 (1993; Zbl 0795.65002); H. Niederreiter and I. E. Shparlinski, Finite Fields Appl. 5, 246-253 (1999; Zbl 0942.11037)]. Reviewer: Zhu Yaochen (Beijing) Cited in 2 ReviewsCited in 18 Documents MSC: 11T23 Exponential sums 11K45 Pseudo-random numbers; Monte Carlo methods 11K38 Irregularities of distribution, discrepancy 65C10 Random number generation in numerical analysis Keywords:finite field; upper bounds; exponential sum; sequences of digital explicit inversive pseudorandom numbers; explicit inversive pseudorandom vectors Citations:Zbl 0795.65002; Zbl 0942.11037 PDFBibTeX XMLCite \textit{H. Niederreiter} and \textit{A. Winterhof}, Acta Arith. 93, No. 4, 387--399 (2000; Zbl 0969.11040) Full Text: DOI EuDML