On the distribution of the power generator modulo a prime power for parts of the period
type: Item
instance of: scholarly article
title: On the distribution of the power generator modulo a prime power for parts of the period
zbMATH Open document ID: 1178.11052
author: Edwin el Mahassni
published in: Boletín de la Sociedad Matemática Mexicana. Third Series
publication date: 2009-04-21T00:00:00Z
review text: 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\).
Mathematics Subject Classification ID: 11K38
Mathematics Subject Classification ID: 11L07
Mathematics Subject Classification ID: 11B50
Mathematics Subject Classification ID: 11K45
zbMATH DE Number: 5545391
zbMATH Keywords: exponential sum
zbMATH Keywords: pseudorandom number generator
zbMATH Keywords: discrepancy
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 5545391