×

Incomplete exponential sums over finite fields and their applications to new inversive pseudorandom number generators. (English) Zbl 0969.11040

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)].

MSC:

11T23 Exponential sums
11K45 Pseudo-random numbers; Monte Carlo methods
11K38 Irregularities of distribution, discrepancy
65C10 Random number generation in numerical analysis
PDFBibTeX XMLCite
Full Text: DOI EuDML