Fixed points of the subset sum pseudorandom number generators (Q6101274): Difference between revisions

Let \(\mathbb{Z}_{t}\) denote the residue ring modulo \(t\). Given \(w\in\mathbb{Z}_{t}\) we expand \(w\) in binary \(w=\overline{u_s\ldots u_1}\), where \(u_i\) represents the \(i\)-th least significant bit of \(w\). Fix an \(r\)-dimensional integer vector \(\mathbf{z}=(z_1, \ldots, z_r) \in \mathbb{Z}_{t}^{r}\) and define the function \(S_{r,t,\mathbf{z}}: \ \mathbb{Z}_{t}\longrightarrow \mathbb{Z}_{t}\) as follows: \[ S_{r,t,\mathbf{z}}(w)=\sum_{i=1}^{r}u_iz_i\in\mathbb{Z}_{t}. \] Define \begin{align*} & F_{r,t}(\mathbf{z})=\sharp\left\{w\in \mathbb{Z}_{t}: \ w=S_{r,t,\mathbf{z}}(w)\right\}, \\ & M_{\nu}(r, t)=\frac{1}{t^{r}}\sum_{\mathbf{z}\in\mathbb{Z}_{t}^{r}}F_{r,t}(\mathbf{z})^{\nu}, \qquad \nu=1,2,\ldots. \end{align*} This paper shows that \[ M_{1}(r, t)=2-\left\lceil t/2^{r} \right\rceil/t \quad \text{for } t\geq 2^{r} \] and \[ M_{\nu}(r, t)\ll \left(t/2^{r}\right)^{\nu-1}\] for prime \(t>2^r\) and any fixed integer \(\nu\geq 1\).