Lattice structure and linear complexity of nonlinear pseudorandom numbers
Let \(q\) be a prime power and \(\mathbb F_q\) be the finite field of order \(q\). Let \(s\geq 1\). the authors first give an extended version of Marsaglia's lattice test as follows: A sequence \(\eta_0, \eta_1,\dots\) over \(\mathbb F_q\) passes the \(s\)-dimensional lattice test if the vectors \(\vec\eta_n- \vec\eta_0\) for \(n\geq 0\) span \(\mathbb F_q^s\), where \(\vec\eta_n= (\eta_n, \eta_{n+1},\dots, \eta_{n+s-1})\) for \(n\geq 0\). Moreover, the linear complexity \(L(\eta_n)\) of a sequence \(\eta_0, \eta_1,\dots, \) over \(\mathbb F_q\) means the least nonnegative integer \(L\) such that there are constants \(\gamma_0,\dots, \gamma_{L-1}\in \mathbb F_q\) satisfying \(\eta_{n+L}+ \gamma_{L-1} \eta_{n+L-1} +\cdots+ \gamma_0\eta_n= 0\) for all \(n\geq L\). The basic result of this paper is that the \(q\)-periodic sequence \(\eta_0, \eta_1,\dots\), over \(\mathbb F_q\) passes the \(s\)-dimensional lattice test if and only if \(s< L(\eta_n)\). The authors also give applications of this result to nonlinear and inverse pseudorandom number generators.
- Lattice structure and linear complexity profile of nonlinear pseudorandom number generators
- On the distribution and lattice structure of nonlinear congruential pseudorandom numbers
- scientific article; zbMATH DE number 2051216
- On the lattice structure of pseudorandom numbers generated over arbitrary finite fields
- scientific article; zbMATH DE number 822311
- Joint linear complexity of multisequences consisting of linear recurring sequences
- Marsaglia's lattice test and non-linear congruential pseudo-random number generators
- Lattice structure and linear complexity profile of nonlinear pseudorandom number generators
- On the linear complexity profile of some new explicit inversive pseudorandom numbers
- On the linear complexity profile of explicit nonlinear pseudorandom numbers.
- On lattice profile of the elliptic curve linear congruential generators
- On the counting function of the lattice profile of periodic sequences
- Successive minima profile, lattice profile, and joint linear complexity profile of pseudorandom multisequences
- Enumeration results on linear complexity profiles and lattice profiles
- On the linear complexity profile of nonlinear congruential pseudorandom number generators with Dickson polynomials
- Counting functions and expected values for the lattice profile at \(n\)
- On the linear complexity profile of nonlinear congruential pseudorandom number generators of higher orders
- On the structure of digital explicit nonlinear and inversive pseudorandom number generators
- On the linear complexity and lattice test of nonlinear pseudorandom number generators
- On k-error linear complexity of some explicit nonlinear pseudorandom sequences
- scientific article; zbMATH DE number 2051216 (Why is no real title available?)
- Measures of pseudorandomness: arithmetic autocorrelation and correlation measure
- On the Structure of Inversive Pseudorandom Number Generators
- On the lattice structure of pseudorandom numbers generated over arbitrary finite fields
- Finite binary sequences constructed by explicit inversive methods
This page was built for publication: Lattice structure and linear complexity of nonlinear pseudorandom numbers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1861173)
