Exponential sums with Dickson polynomials
Given a polynomial \(F(X)\in F_p[X]\) of degree at least \(2\), the \textit{nonlinear congruential generator} \((x_n)\) of elements of \(F_p\) is defined by the recurrence relation \[ x_{n+1} \equiv F(x_n) \pmod p, \qquad n = 0, 1, \dots, \] with some initial value \(x_0\). In \textit{H. Niederreiter} and \textit{I. E. Shparlinski} [Finite Fields Appl. 5, No.~3, 246--253 (1999; Zbl 0942.11037)] a new method has been invented to estimate exponential sums with such sequences for arbitrary polynomials \(F(X)\) and thus to study the distribution of the sequence. Unfortunately, for general polynomials, this method leads to rather weak bounds. However, in the special case of the \textit{inversive congruential generator} this method leads to a much stronger bound, see \textit{H. Niederreiter} and \textit{I. E. Shparlinski} [Math. Comput. 70, No.~236, 1569--1574 (2001; Zbl 0983.11048)]. For another special class of polynomials, namely for \textit{monomials} an alternative approach, producing much stronger bounds has been proposed in [\textit{J. B. Friedlander, J. S. Hansen} and \textit{I. E. Shparlinski}, Nathanson, Melvyn B. (ed.), Unusual applications of number theory. Proceedings of the DIMACS workshop held at Rutgers University, Piscataway, NJ, USA, DIMACS. Series in Discrete Mathematics and Theoretical Computer Science 64, 71--79 (2004; Zbl 1086.11039)] and \textit{J. B. Friedlander} and \textit{I. E. Shparlinski} [Math. Comput. 70, No.~236, 1575--1589 (2001; Zbl 1029.11042)]. This article deals with another special case of the nonlinear congruential pseudorandom number generator constructed via \textit{Dickson polynomials}. The authors apply the method for the power generator mentioned above. However, the results are weaker since Dickson polynomials don't have several specific properties of monomials. However, in an important special case, using a bound from \textit{W.-C. Li} [Finite Fields Appl. 12, No.~1, 1--15 (2006; Zbl 1103.11025)], they obtain a result of the same strength as for the power generator. Reviewer's comment. A modification of the method of this paper has recently been used by the reviewer and J. Gutierrez to estimate exponential sums with \textit{Rédei} functions.
nonlinear pseudorandom number generators
scientific article; zbMATH DE number 5004383