Scrambled linear pseudorandom number generators

DOI10.1145/3460772zbMATH Open1486.65003arXiv1805.01407OpenAlexW3202613539WikidataQ113309875 ScholiaQ113309875MaRDI QIDQ126971FDOQ126971

Authors: David Blackman, Sebastiano Vigna, David Blackman, Sebastiano Vigna 

Publication date: 3 May 2018

Published in: ACM Transactions on Mathematical Software (Search for Journal in Brave)

Abstract: $mathbf{F}_2$-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 $mathbf{F}_2$-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.

Full work available at URL: https://arxiv.org/abs/1805.01407

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

zbMATH Keywords

pseudorandom number generators

Mathematics Subject Classification ID

Random number generation in numerical analysis (65C10) Shift register sequences and sequences over finite alphabets in information and communication theory (94A55)

Cited In (12)

• A system of interacting neurons with short term synaptic facilitation
• A matrix PRNG with s-box output filtering
• Further scramblings of Marsaglia's \(\mathsf{xorshift}\) generators
• Tropical Feynman integration in the Minkowski regime
• dqrng
• An experimental exploration of Marsaglia's \texttt{xorshift} generators, scrambled
• A new test for Hamming-weight dependencies
• Scrambling additive lagged-Fibonacci generators
• MaD0: an ultrafast nonlinear pseudorandom number generator
• Feistel-inspired scrambling improves the quality of linear congruential generators
• xorshift1024*, xorshift1024+, xorshift128+ and xoroshiro128+ fail statistical tests for linearity
• Fast lattice reduction for \(\mathbb F_2\)-linear pseudorandom number generators

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)