The Uniform Distribution of Sequences Generated by Iteration of Polynomials

Emil Lerner

Paper 2015/296

The Uniform Distribution of Sequences Generated by Iteration of Polynomials

Emil Lerner

Abstract

Consider a collection $f$ of polynomials $f_{i} (x)$ , $i = 1, \dots, s$ , with integer coefficients such that polynomials $f_{i} (x) - f_{i} (0)$ , $i = 1, \dots, s$ , are linearly independent. Denote by $D_{m}$ the discrepancy for the set of points $(\frac{f_{1} (x) mod m}{m}, \dots, \frac{f_{s} (x) mod m}{p^{n}})$ for all $x \in {0, 1, \dots, m}$ , where $m = p^{n}$ , $n \in N$ , and $p$ is a prime number. We prove that $D_{m} \to 0$ as $n \to \infty$ , and $D_{m} < c_{1} (\log \log m)^{- c_{2}}$ , where $c_{1}$ and $c_{2}$ are positive constants that depend only on the collection of $f_{i}$ . As a corollary, we obtain an analogous result for iterations of any polynomial (with integer coefficients) whose degree exceeds~1. Certain results on the uniform distribution were known earlier only for some classes of polynomials with $s ⩽ 3$

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Preprint. MINOR revision.
Keywords: pseudo-randomness polynomial PRNG uniform distribution
Contact author(s): neex emil @ gmail com
History: 2015-04-01: received
Short URL: https://ia.cr/2015/296
License: CC BY

BibTeX

@misc{cryptoeprint:2015/296,
      author = {Emil Lerner},
      title = {The Uniform Distribution of Sequences Generated by Iteration of Polynomials},
      howpublished = {Cryptology {ePrint} Archive, Paper 2015/296},
      year = {2015},
      url = {https://eprint.iacr.org/2015/296}
}