On pseudorandom numbers from multivariate polynomial systems
type: Item
instance of: scholarly article
title: On pseudorandom numbers from multivariate polynomial systems
zbMATH Open document ID: 1254.11076
author: Alina Ostafe
author: Elena Pelican
author: Igor E. Shparlinski
published in: Finite Fields and their Applications
publication date: 2010-10-11T00:00:00Z
review text: This paper deals with sequences of vectors \(\mathbf{u}_n=(u_{n,1,},\ldots,u_{n,m})\in\mathbb{F}_p^m\) generated by multivariate polynomial systems. The vectors \(\mathbf{u}_n\) are defined by a recurrence congruence modulo the prime \(p\), \[ u_{n+1,i}=f_i(u_{n,1},\ldots,u_{n,m}),\;n=0,1,\ldots, \] with initial values \(\mathbf{u}_0=(u_{0,1},\ldots,u_{0,m})\), where \(f_1(X_1,\ldots,X_m),\ldots,f_m (X_1,\ldots,X_m)\) are polynomials over \(\mathbb{F}_p\). The authors derive bounds on exponential sums along the orbits of such polynomial systems. These bounds hold for essentially arbitrary polynomial systems with sufficiently long orbits, and they can be applied, via the Erdős-Turán-Koksma inequality, to deriving discrepancy bounds for sequences of pseudorandom vectors based on the sequence of the \(\mathbf{u}_n\). The approach in this paper, in comparison to previous results, does not require control of the degree growth of the iterations of the polynomial system.
reviewed by: Peter Kritzer
Mathematics Subject Classification ID: 11K45
Mathematics Subject Classification ID: 11T23
Mathematics Subject Classification ID: 37A45
Mathematics Subject Classification ID: 37F10
zbMATH DE Number: 5798562
zbMATH Keywords: multivariate polynomial
zbMATH Keywords: pseudorandom number generator
zbMATH Keywords: discrepancy
MaRDI profile type: Publication
full work available at URL: j.ffa.2010.05.002
OpenAlex ID: W1970305556
cites work: Cryptography and Coding
cites work: Predicting nonlinear pseudorandom number generators
cites work: Information Security and Privacy
cites work: Sequences, discrepancies and applications
cites work: Reconstructing Truncated Integer Variables Satisfying Linear Congruences
cites work: Q4502614
cites work: Attacking the Pollard Generator
cites work: Q4474254
cites work: Inferring sequences produced by a linear congruential generator on elliptic curves missing high-order bits
cites work: Lattice reduction: a toolbox for the cryptoanalyst
cites work: Deciphering a linear congruential encryption
cites work: How to predict congruential generators
cites work: Q4767350
cites work: Q3974094
cites work: Quasi-Monte Carlo methods and pseudo-random numbers
cites work: Q4003879
cites work: On the distribution and lattice structure of nonlinear congruential pseudorandom numbers
cites work: On the distribution of inversive congruential pseudorandom numbers in parts of the period
cites work: Q4426679
cites work: Exponential sums for nonlinear recurring sequences
cites work: Multivariate permutation polynomial systems and nonlinear pseudorandom number generators
cites work: Pseudorandom Vector Sequences Derived from Triangular Polynomial Systems with Constant Multipliers
cites work: On the degree growth in some polynomial dynamical systems and nonlinear pseudorandom number generators
cites work: Pseudorandom numbers and hash functions from iterations of multivariate polynomials
cites work: On the average distribution of pseudorandom numbers generated by nonlinear permutations
cites work: Q5297487
DOI: 10.1016/J.FFA.2010.05.002
Recommended article: Multivariate permutation polynomial systems and nonlinear pseudorandom number generators
Recommended article: Pseudorandom numbers and hash functions from iterations of multivariate polynomials
Recommended article: Q4474254
Recommended article: Pseudorandom Vector Sequences Derived from Triangular Polynomial Systems with Constant Multipliers
Recommended article: Pseudorandom Bits for Polynomials
Recommended article: On the generation of random stable polynomials
Recommended article: Pseudorandom generators for low degree polynomials
Recommended article: Pseudorandom generators for polynomial threshold functions
Recommended article: Quasi-random multilinear polynomials
description: scientific article; zbMATH DE number 5798562