Lattice structure and linear complexity profile of nonlinear pseudorandom number generators
The authors extend a generalized version of Marsaglia's lattice test for sequences over finite fields to segments of sequences over an arbitrary field \(\mathbb{K}\) and give the relation between lattice test and linear complexity profile for such sequences. For given \(s\geq 1\) and \(N\geq 1\) we say that a sequence \((\eta_n)\) over \(\mathbb{K}\) (it is not necessarily periodic) passes the \(s\)-dimensional \(N\)-lattice test if the vectors \(\vec\eta_n- \vec\eta_0\) \((1< n< N-s) \operatorname {span} \mathbb{K}^s\), where \(\vec\eta_n= (\eta_n, \eta_{n+1},\dots, \eta_{n+s-1})\). Let \(L(N)= L((\eta_n),N)\) be the greatest one among such \(s\). Further, the linear complexity profile \(L(N)= L((\eta_n),N)\) is defined by the least order of a linear recurrence relation over \(\mathbb{K}\) satisfied by the first \(N\) terms of \((\eta_n)\). The authors prove that either \(S(N)= \min(L(N), N+1-L(N))\), or \(S(N)= \min(L(N), N+1- L(N))-1\), and so this lattice test and linear complexity profile provide essentially equivalent quality measures for randomness.
- scientific article; zbMATH DE number 2051216
- Lattice structure and linear complexity of nonlinear pseudorandom numbers
- Marsaglia's lattice test and non-linear congruential pseudo-random number generators
- On the linear and nonlinear complexity profile of nonlinear pseudorandom number generators
- On the structure of digital explicit nonlinear and inversive pseudorandom number generators
- Joint linear complexity of multisequences consisting of linear recurring sequences
- On Marsaglia's lattice test for pseudorandom numbers
- On the \(N\)th linear complexity of automatic sequences
- Hamming correlation of higher order
- On the linear complexity profile of some new explicit inversive pseudorandom numbers
- On the linear complexity profile of explicit nonlinear pseudorandom numbers.
- Lattice structure and linear complexity of nonlinear pseudorandom numbers
- Pseudorandom sequences derived from automatic sequences
- The lattice structure of nonlinear congruential 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
- Continued fraction for formal Laurent series and the lattice structure of sequences
- 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 the lattice structure of inversive PRNG via the additive order
- Recent results on recursive nonlinear pseudorandom number generators (invited paper)
- scientific article; zbMATH DE number 2051216 (Why is no real title available?)
- Measures of pseudorandomness: arithmetic autocorrelation and correlation measure
- On the linear and nonlinear complexity profile of nonlinear pseudorandom number generators
- scientific article; zbMATH DE number 2124952 (Why is no real title available?)
- Lattice computations for random numbers
- On the Structure of Inversive Pseudorandom Number Generators
- Some notes on the pseudorandomness of Legendre symbol and Liouville function
- On the lattice structure of a nonlinear generator with modulus \(2^{\alpha}\)
This page was built for publication: Lattice structure and linear complexity profile of nonlinear pseudorandom number generators
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1396702)
