On the lattice structure of pseudorandom numbers generated over arbitrary finite fields
Let \(\mathbb{F}_q\) be the finite field of order \(q=p^r\), where \(r\in\mathbb N\) and \(p\) is prime, and let \(\{\eta_n\}_{n=0}^\infty\) be a periodic sequence of elements of \(\mathbb F_q\) with period \(q\). Then the map \(\xi_n\mapsto \eta_n\) for \(n=0,1,\ldots\), where \(\{\xi_0,\xi_1,\ldots, \xi_{q-1}\}\) is any ordering of the elements of \(\mathbb F_q\) with \(\xi_0=0\) and \(\xi_{n+q}= \xi_n\) for \(n=0,1,\ldots\), can be represented by a uniquely determined polynomial \(g\in\mathbb F_q[x]\) with \(\deg(g)< q\), and so \[ \eta_n= g(\xi_n) \quad\text{for}\;n=0,1,\ldots\;.\tag \(*\) \] \textit{J. Eichenauer, H. Grothe}, and \textit{J. Lehn} [Metrika 35, 241--250 (1988; Zbl 0653.65006)] showed that a congruential generator modulo \(p\) passes the \(s\)-dimensional lattice test proposed by \textit{G. Marsaglia} [Applications of number theory to numerical analysis, Proc. Symp. Univ. Montreal 1971, New York: Academic Press, 249--285 (1972; Zbl 0266.65007)] if and only if \(s\leq \deg(g)\). In the present paper the authors prove that the generator \((*)\) over \(\mathbb F_q\) passes the \(s\)-dimensional lattice test if and only if the polynomials \(\varphi_0(g), \varphi_1(g),\ldots, \varphi_{s-1}(g)\) are linearly independent over \(\mathbb F_q\), where \(\varphi_j(g)(x)= g(x+\xi_j)- g(\xi_j)\) for \(j=0,\ldots, q-1\). Furthermore, they also derive from this criterion necessary conditions and a sufficient condition for passing the \(s\)-dimensional lattice test.
- scientific article; zbMATH DE number 822311
- scientific article; zbMATH DE number 426123
- Lattice structure and linear complexity of nonlinear pseudorandom numbers
- Remarks on nonlinear congruential pseudorandom numbers
- On lattice profile of the elliptic curve linear congruential generators
- Tables of linear congruential generators of different sizes and good lattice structure
- Marsaglia's lattice test and non-linear congruential pseudo-random number generators
- Counting functions and expected values for the lattice profile at \(n\)
- Bad Lattice Structures for Vectors of Nonsuccessive Values Produced by Some Linear Recurrences
- A matrix linear congruent generator over a Galois ring of odd characteristic
- Remarks on nonlinear congruential pseudorandom numbers
- On the linear complexity profile of explicit nonlinear pseudorandom numbers.
- Lattice structure and linear complexity of nonlinear pseudorandom numbers
- Normality of the Thue-Morse function for finite fields along polynomial values
- A computational algebraic geometry approach to analyze pseudo-random sequences based on Latin squares
- Improving results on the pseudorandomness of sequences generated via the additive order of a finite field
- Generalized explicit inversive generators of small \(p\)-weight degree
- On the structure of digital explicit nonlinear and inversive pseudorandom number generators
- scientific article; zbMATH DE number 426145 (Why is no real title available?)
- Randomness extraction in finite fields F_{p^n}
- Structure of Pseudorandom Numbers Derived from Fermat Quotients
- scientific article; zbMATH DE number 2051216 (Why is no real title available?)
- scientific article; zbMATH DE number 822311 (Why is no real title available?)
- scientific article; zbMATH DE number 7594564 (Why is no real title available?)
- Connected components of the graph generated by power maps in prime finite fields
- On finite pseudorandom lattices of \(k\) symbols
- Finite binary sequences constructed by explicit inversive methods
This page was built for publication: On the lattice structure of pseudorandom numbers generated over arbitrary finite fields
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5941760)
