New trends in pseudorandom number generation

The goal of this talk is to present the state-of-the-art construction of pseudorandom number generators (PRNGs) using multivariate polynomials or rational functions. We recall that all previously known results are nontrivial only for those polynomial generators that produce sequences of extremely large period, which could be hard to achieve in practice. The reason behind this is that typically the degree or the number of terms of iterated polynomials grows exponentially, and that in all previous results the saving over the trivial bound has been logarithmic. To overcome these limitations, we present some new constructions of multivariate polynomial dynamical systems with a polynomial degree growth of its iterates (instead of the “typical” exponential growth) or a sparse representation. Dynamical systems generated by iterations of these polynomials have proved to admit good estimates of exponential sums along their orbits, which immediately imply nontrivial estimates on the discrepancy of such pseudorandom vectors. Constructing “good” PRNGs has made it clear that further progress here can only be achieved if more detailed information about the algebraic structure of polynomial iterates (such as irreducibility, non-singularity, etc) is available. Motivated by these applications we also discuss some (mostly widely open) questions associated to algebraic dynamical systems generated by multivariate polynomials or rational functions, which are of independent interest.