On the distribution of the power generator modulo a prime power for parts of the period (Q1012405)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the distribution of the power generator modulo a prime power for parts of the period |
scientific article |
Statements
On the distribution of the power generator modulo a prime power for parts of the period (English)
0 references
21 April 2009
0 references
Let \(e\geq 2\) and \(m=p^r\) where \(p\) is a prime such that \(e\) is regular modulo \(p\). Assume that the sequence \((u_n)\) given by the recurrence relation \[ u_n\equiv u_{n-1}^e \pmod m,\quad 0\leq u_n\leq m-1,\quad n=1,2,\dots, \] with the initial value \(u_0=\vartheta\), is periodic with period \(\tau\), where \(1\leq N\leq \tau\). For an integer vector \(\mathbf{a}=(a_1,\dots,a_s)\in \mathbb{Z}^s\) we define the exponential sum \[ S(\mathbf{a},r)=\sum_{n=0}^{N-1}e_r\left(\sum_{i=1}^sa_iu_{n+i}\right), \] where \(e_r(z)=\exp(2\pi i z/p^r)\). Furthermore let \(D_s\) denote the discrepancy of the points \[ \left(\left\{\frac{u_n}{p^r}\right\},\dots,\left\{\frac{u_{n+s-1}}{p^r}\right\}\right), \quad n=1,\dots,N <\tau. \] Then, for every integer \(s\), any \(\varepsilon>0\), and every vector \(\mathbf{a}=(a_1,\dots,a_s)\in \mathbb{Z}^s\) with \(\gcd(a_0,\dots,a_{s-1},p^r)=\mu\), we have \[ \left|S(\mathbf{a},r)\right|\ll N^{1/2}m^{1/2}(m/\mu)^{-1/4s(s+1)+\varepsilon} \] and \[ D_s\ll N^{-1/2}m^{1/2-1/4s(s+1)+\varepsilon}, \] where the implied constant depends at most on \(p\), \(s\) and \(\varepsilon\).
0 references
exponential sum
0 references
pseudorandom number generator
0 references
discrepancy
0 references