Scrambled linear pseudorandom number generators
From MaRDI portal
Abstract: -linear pseudorandom number generators are very popular due to their high speed, to the ease with which generators with a sizable state space can be created, and to their provable theoretical properties. However, they suffer from linear artifacts that show as failures in linearity-related statistical tests such as the binary-rank and the linear-complexity test. In this paper, we give two new contributions. First, we introduce two new -linear transformations that have been handcrafted to have good statistical properties and at the same time to be programmable very efficiently on superscalar processors, or even directly in hardware. Then, we describe some scramblers, that is, nonlinear functions applied to the state array that reduce or delete the linear artifacts, and propose combinations of linear transformations and scramblers that give extremely fast pseudorandom number generators of high quality. A novelty in our approach is that we use ideas from the theory of filtered linear-feedback shift registers to prove some properties of our scramblers, rather than relying purely on heuristics. In the end, we provide simple, extremely fast generators that use a few hundred bits of memory, have provable properties, and pass strong statistical tests.
Recommendations
- Scrambling additive lagged-Fibonacci generators
- Feistel-inspired scrambling improves the quality of linear congruential generators
- An experimental exploration of Marsaglia's \texttt{xorshift} generators, scrambled
- Combined generators with components from different families
- Stochastic investigations of pseudo-random number generators
Cited in
(12)- Tropical Feynman integration in the Minkowski regime
- An experimental exploration of Marsaglia's \texttt{xorshift} generators, scrambled
- Feistel-inspired scrambling improves the quality of linear congruential generators
- Fast lattice reduction for \(\mathbb F_2\)-linear pseudorandom number generators
- A system of interacting neurons with short term synaptic facilitation
- dqrng
- Further scramblings of Marsaglia's \(\mathsf{xorshift}\) generators
- Scrambling additive lagged-Fibonacci generators
- A matrix PRNG with s-box output filtering
- A new test for Hamming-weight dependencies
- xorshift1024*, xorshift1024+, xorshift128+ and xoroshiro128+ fail statistical tests for linearity
- MaD0: an ultrafast nonlinear pseudorandom number generator
This page was built for publication: Scrambled linear pseudorandom number generators
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q126971)
