Multivariate permutation polynomial systems and nonlinear pseudorandom number generators (Q973960)

Let \(\mathbb{F}\) be an arbitrary field and let the polynomials \(g_i, h_i \in \mathbb{F}[X_{i+1}, \dots ,X_m]\), \(i = 0, \dots ,m - 1\), satisfying the following conditions: each polynomial \(g_i\) has a unique leading monomial \(X_{i+1}^{s_{i,i+1}} \dots X_m^{s_{i,m}}\). One can construct a dynamical system \(F= \left\{{f_0, \dots, f_m}\right\}\) of \(m + 1\) polynomials in the ring \(\mathbb{F}[X_0, \dots ,X_m]\) defined in the following way: \[ f_0(X_0,\dots,X_m) = X_0g_0(X_1, \dots ,X_m) + h_0(X_1, \dots ,X_m), \] \[ f_1(X_0, \dots ,X_m) = X_1g_1(X_2, \dots ,X_m) + h_1(X_2, \dots ,X_m), \dots, \] \[ f_{m-1}(X_0, \dots ,X_m) = X_{m-1}g_{m-1}(X_m) + h_{m-1}(X_m), \] \[ f_m(X_0, \dots ,X_m) = aX_m + b, \] where \(a, b \in \mathbb{F}, a \neq 0\), and \(g_i, h_i \in \mathbb{F}[X_{i+1}, \dots ,X_m]\), \(i = 0, \dots ,m - 1\). For each \(i = 0, \dots ,m\) define the \(k\)-th iteration of the polynomials \(f_i\) by the recurrence relation \[ f_i^{(0)} = X_i, f_i^{(k)} = f_i(f_0^{(k-1)}, \dots , f_m^{(k-1)}) , k = 0, 1, \dots. \] In this paper the author studies a class of dynamical systems generated by iterations of multivariate permutation polynomial systems which lead to polynomial growth of the degrees of these iterations. Using these estimates and the same techniques studied previously by some other authors for inversive generators, the author is able to bound exponential sums along the orbits of these dynamical systems and show that they admit much stronger estimates on average over all initial values \(v \in \mathbb F_p^{m+1}\) than in the general case and thus can be of use for pseudorandom number generation.