New trends in pseudorandom number generation

Alina Ostafe

Research output: Contribution to conferenceAbstract

Abstract

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.
Original languageEnglish
Pages128
Number of pages1
Publication statusPublished - 2012
EventInternational Conference on Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing (10th : 2012) - Sydney
Duration: 13 Feb 201217 Feb 2012

Conference

ConferenceInternational Conference on Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing (10th : 2012)
CitySydney
Period13/02/1217/02/12

Keywords

  • Monte Carlo simulation
  • Statistical analysis
  • Computer science

Fingerprint Dive into the research topics of 'New trends in pseudorandom number generation'. Together they form a unique fingerprint.

Cite this