Source-linked AI summary
Scrambled Linear Pseudorandom Number Generators
David Blackman, Sebastiano Vigna
TL;DR
F_2-linear generators combine speed and provable properties with failures on linearity-related tests. This paper designs efficient linear engines and nonlinear scramblers, analyzes scramblers using filtered-LFSR theory, and combines them into fast generators that pass strong statistical tests, while some practical and theoretical limitations remain.
Problem
F_2-linear generators are fast and mathematically analyzable but fail binary-rank and linear-complexity tests because their linear structure is detectable.
Method
The paper combines two efficient linear-engine designs with nonlinear scramblers and analyzes scrambler properties using filtered-LFSR theory.
Results
The resulting generators include xoshiro256++, which emits a value in 0.86 ns, passes the authors’ known statistical tests, and is 3-dimensionally equidistributed.
Takeaways & Limitations
The combinations provide fast, high-quality generators with different tradeoffs in speed, state size, and statistical quality.
Takeaways & Limitations
Not all discussed generator combinations are practically useful, and symbolic computation leaves the exact degree bound for the ++ scrambler unresolved.
Abstract
from arXiv · showhide
$\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.
1 INTRODUCTION
The paper targets linear artifacts in fast, provable F_2-linear generators by combining new linear engines with nonlinear scramblers. The resulting generators offer tradeoffs among speed, state size, and statistical quality.
- Motivation: F_2-linear generators are fast, support large full-period state spaces, and offer mathematically provable properties, but fail binary-rank and linear-complexity tests.These tests are designed to detect the generators’ linear structure.
- Motivation: Scrambling can mitigate linear artifacts, but multiplication or addition may leave lower bits unchanged or only slightly modified.Those bits can still fail linearity tests in isolation or with too few good bits.
- Approach: The paper combines linear engines and scramblers to provide different tradeoffs in speed, space usage, and statistical quality.The approach seeks fast generators with provable properties.
- Results: 0.86 ns is the xoshiro256++ generation time on an Intel Core i7-8700B, while the generator passes reported tests and is 3-dimensionally equidistributed.Eight parallel instances reduce the time to 0.30 ns.
- Results: 0.78 ns is the xoshiro256+ generation time for floating-point-oriented use, with no linear bias in the resulting values from its upper 53 bits.Parallel instances reduce the time to 0.22 ns.
- Scope: Smaller-state xoroshiro128 variants provide similar timings and properties, while the approach also supplies 32-bit and fast, reasonable 16-bit generators.The paper also describes higher-dimensional generators, mainly for theoretical reasons.
2 ORGANIZATION OF THE PAPER
The paper presents generator code and practical information early, then develops the engines, scramblers, combinations, and mathematical analyses in later sections. Its theory covers period, equidistribution, and scrambler behavior.
- Scope: The paper focuses mainly on 64-bit generators with state sizes of k·w bits, while also providing 32-bit combinations.Here w denotes word size and k≥2.
- Organization: The organization prioritizes immediate access to code and basic generator information, postponing theoretical considerations to the second part.This structure is intended to make practical material available quickly.
- Core design: A generator combines a linear engine that advances internal state with a scrambler that computes the actual output.The scrambler is usually applied to the current state to support internal CPU parallelism.
- Organization: Sections 3–5 introduce engines, scramblers, their combinations, speed, statistical results, and a guide for choosing generators.The paper distinguishes the underlying engine from the overall generator when discussing combinations.
- Theory: Sections 6–7 use word polynomials to analyze characteristic polynomials, full period, and equidistribution.Word polynomials are polynomials on w×w matrices associated with a linear engine.
- Theory: From Section 9 onward, filtered-LFSR theory supplies exact scrambler results and heuristics supported by extensive symbolic computation.The analysis gives a more rigorous foundation to choices made earlier in the paper.
3 LINEAR ENGINES
The paper introduces xoroshiro and xoshiro linear engines built from shifts, rotations, and xors, with computation paths designed for efficient implementation and parallelism. Their applicable state sizes differ.
- Engine design: Rotations provide better state diffusion than shifts because no operand bit is discarded, while modern compilers can compile them to single instructions.The engines use rotations alongside shifts and xors.
- xoroshiro: The xoroshiro update uses two computation paths of length two with one shared dependency, supporting parallelizability inside superscalar CPUs.Its base transformation combines a rotation, a shift, and another rotation.
- xoroshiro: The xoroshiro state transformation cyclically updates words, applying the basic form to endpoint words and shifting the remaining words.The structure is designed for a simple and efficient computation path.
- Implementations: Figure 1 instantiates xoroshiro128 with two nonzero 64-bit state words, while Figure 2 instantiates xoroshiro1024 with sixteen such words and an index p in [0..16).These are code-level state layouts for xoroshiro variants.
- xoshiro: The xoshiro transformation uses a shift and a rotation and updates all state words on every iteration.This makes xoshiro suitable for moderate state sizes.
- xoshiro: Figures 4 and 5 show xoshiro256 and xoshiro512 implementations with four and eight 64-bit state words, respectively.The xoshiro update shifts one word, xors words in sequence, and rotates the last word.
- Limitations: Xoshiro is undefined for a 2w-bit state and too slow for a 16w-bit state because each iteration requires many writes.The limitation follows from its update structure.
4 SCRAMBLERS
Scramblers are nonlinear output mappings that improve a linear engine’s raw output while preserving a fast, provable generator design. The section distinguishes their mechanisms and notes that low output bits can retain detectable linear structure.
- Scramblers map the linear engine’s state to a w-bit output, improving raw-output quality while retaining useful provable properties of linear transformations.
- + scrambler: The + scrambler adds two state words in Z/2^wZ, with word selection affecting the resulting generator’s statistical quality.
- + scrambler: The + scrambler’s lowest output bit follows the same linear recurrence as the underlying generator, making it a weak scrambler.
- + scrambler: Higher bits of the + output still follow a linear recurrence, but their linear complexity quickly becomes undetectable.
- * scrambler: The * scrambler multiplies a selected state word by an odd constant, making the mapping bijective while leaving some low bits vulnerable to linear recurrence.
- ++ scrambler: The ++ scrambler sums two words, rotates the result left, and adds the first word; word order and rotation amount are design parameters.
- ** scrambler: The ** scrambler applies multiply-rotate-multiply using two odd multipliers and a rotation, with multipliers of the form 2^s + 1 offering fast implementations.
5 COMBINING LINEAR ENGINES AND SCRAMBLERS
The paper evaluates combinations of linear engines and scramblers using BigCrush and a Hamming-weight dependency test, then compares their speed, statistical behavior, and practical tradeoffs. Strong scramblers remove detectable bias in several engines, while weaker combinations retain specific linear or Hamming-weight artifacts.
- Testing methodology: The evaluation combines BigCrush, reversed-output testing, and a Hamming-weight dependency test that can expose biases missed by TestU01.BigCrush failures are reported systematically across seeds, while the Hamming-weight test runs until 10^15 bytes or until p<10^-20.
- 64-bit combinations: The + scrambler removes detectable bias from xoshiro generators but improves xoroshiro+ resilience by almost three orders of magnitude.The comparison concerns the Hamming-weight dependency test described in the section.
- 64-bit combinations: The * scrambler handles Hamming-weight dependencies better than linear dependencies, and xoroshiro128* still fails MatrixRank when reversed.Switching to the ++ and ** scramblers leaves no detectable bias in the reported tests.
- 32-bit combinations: For 32-bit xoroshiro engines, * is recommended because the faster + scrambler is too weak and its low-bit linearity is detected by BigCrush.The lowest bits of generators using a weak scrambler remain linear.
- Choosing a generator: For smaller state, xoroshiro128 variants provide similar timings and properties, although xoroshiro128+ shows Hamming-weight bias only after 5 TB of data.For larger state, the paper recommends xoshiro512 variants before xoroshiro1024 variants; 32-bit recommendations favor xoshiro128++ and xoshiro128**.
6 POLYNOMIALS AND FULL PERIOD
The section uses characteristic and word polynomials to identify full-period linear engines and analyze how state words depend on previous outputs. In the noncommutative case, word polynomials still support characteristic-polynomial computation, but not the same recurrence guarantees.
- Full period: A linear engine has full period 2^n−1 exactly when its characteristic polynomial is primitive over Z/2Z.Enumerating parameter choices and checking polynomial primitivity discovers all full-period engines.
- Design considerations: The polynomial weight criterion is only one signal: relationships among all state bits must also be considered when evaluating a linear engine.The criterion applies technically to the represented recurrence, not necessarily to the complete state-bit behavior.
- Word polynomials: Word polynomials extend characteristic-polynomial computation to block-structured matrices, treating commuting matrix blocks like scalar coefficients.This approach can simplify determinants of large matrices with zero and commuting nonzero blocks.
- Recurrences: The resulting recurrence predicts every selected state word from its previous k outputs, because each word block satisfies the same polynomial relation.The recurrence is useful for assessing predictability of output words, not merely for advancing the state.
- The noncommutative case: Noncommuting blocks prevent the polynomial from directly expressing the linear transformation as the usual recurrence, although word polynomials still compute the characteristic polynomial.Recent noncommutative determinant results recover a word polynomial under stated block-commutation conditions.
- Predictability: 4/5 of state-word bits are predictable for xoroshiro128, versus about 1/2 for xoroshiro1024, using the noncommutative polynomial.For xoshiro256, one word is exactly predictable and about two thirds of the bits are predictable in the other words; xoshiro512 has a similar pattern except for its last word.
7 EQUIDISTRIBUTION
The section characterizes equidistribution for the linear engines and their scramblers, then proves dimension-specific guarantees for + and ++ constructions. These guarantees are useful but do not generally extend to the maximum possible dimension.
- Linear engines: Full period is insufficient for maximum-dimensional equidistribution when an engine updates multiple state positions, so different words can have different properties.The authors test maximum-dimensional equidistribution by checking invertibility of matrices formed from successive powers of the update matrix.
- Scrambler effects: Bijective * and ** scramblers preserve full-output equidistribution, making their generators k-dimensionally equidistributed.This preservation applies to the full output; subsets of output bits can behave differently.
- Proof technique: The + and ++ analyses convert target-output conditions into arithmetic and binary constraints, then count state assignments satisfying those constraints.The method solves state variables through linear algebra before selecting free parameters to satisfy both constraint systems.
- xoroshiro: A xoroshiro+ generator using the first and last state words is (k−1)-dimensionally equidistributed.The corresponding xoroshiro++ result also holds when scrambling the last and first words.
- xoroshiro: For k=2, xoroshiro++ remains 1-dimensionally equidistributed even when the first and last words are used in the opposite order.The stronger ordering result is restricted to k=2.
- xoshiro: A 4-word xoshiro+ or xoshiro++ generator can be 3-dimensionally equidistributed, while an 8-word xoshiro++ construction can be 7-dimensionally equidistributed.The stated word choices are first and last for the 4-word constructions, and third and first for the 8-word construction.
8 ESCAPING ZEROLAND
Figure 7 examines how quickly the generators escape from zeroland, where initially sparse states become states with approximately half their bits set. Scrambling reduces but does not eliminate this detectable behavior.
- Escape measure: Figure 7 measures escape time by the ratio of ones in a window of four consecutive 64-bit values.Linear engines take time to diffuse an initially small number of set bits, and scrambling reduces but does not eliminate the effect.
9 A THEORETICAL ANALYSIS OF SCRAMBLERS
The paper analyzes scramblers through filtered-LFSR ideas, Boolean-function structure, and linear complexity. It finds that cancellation is usually rare for primitive engines, but polynomial degree alone does not ensure resistance to joint linearity tests.
- Framework: Filtered-LFSR theory frames each scrambler as Boolean functions applied to outputs of an underlying linear engine.The paper contrasts this framework with its multiple primitive engines, combined outputs, and implementation constraints.
- Representation: Formal-series coefficients reproduce successive output bits, enabling exact recurrence analysis in the splitting-field representation.The approach represents each bit’s generating function and uses its coefficients as the corresponding output sequence.
- Representation: 6, 15, and 41 coefficients equal the linear complexities of three xorshift+ output bits, but the representation becomes unmanageable beyond very small state arrays.The limitation arises because carries rapidly increase the number of terms in the splitting-field representation.
- Cancellation: Unless the linear engine is tiny, cancellation is extremely rare when its characteristic polynomial is primitive.This conclusion comes from symbolic and Berlekamp–Massey measurements on generators up to 12-bit generators with 24 bits of state.
- Test resistance: High polynomial degree does not guarantee passing linear-complexity or binary-rank tests because those tests depend on the joint output of multiple Boolean functions.The paper also notes that excessively many or overly regular monomials can remain problematic.
- Scrambler behavior: The 3x scrambler performs poorly empirically because its theorem implies excessive cancellation of monomials.By contrast, the analyzed * structure avoids polynomial degree loss when combining bits, while the 3x result illustrates that degree behavior can have practical consequences.
- Scrambler behavior: The ++ scrambler’s degree bound remains unresolved, with symbolic computation suggesting 2^w−3 against the proven bound 2^w−1.The paper presents proving the tighter bound as an open problem.
- Scrambler behavior: For multiplication-based scramblers, low-bit degree and linear-complexity behavior vary by parameters, and the ** scrambler is not sufficiently powerful for xoroshiro64 at 32 bits.The paper reports polynomial degree loss in some parameter settings and a separate empirical weakness for xoroshiro64.
10 CONCLUSIONS
The paper concludes that combining xoroshiro or xoshiro engines with suitable scramblers yields fast, high-quality generators across hardware and state-size settings. It also identifies unresolved theory around Hamming-weight dependencies and ANF structure.
- Conclusions: Suitable xoroshiro/xoshiro scramblers provide fast, high-quality generators used or scheduled for inclusion in several programming languages and hardware platforms.Examples include Propeller 2, Erlang, Lua, GNU Fortran, and planned Java 17 support.
- Open problems: A complete theory of scramblers remains open because Hamming-weight dependencies arise from collective Boolean-function behavior, not isolated bits.The paper specifically calls for a model explaining elimination of these dependencies.
- Conclusions: Rotation-free variants may extend ++ and ** scramblers to contexts where rotations are unavailable or expensive.The paper suggests replacing rotation with xoring x and x≫r, which can also increase lower-bit linear complexity.
- Open problems: Filtered-LFSR literature may help replace some symbolic small-state computations with proofs or closed forms.The paper points to prior lower bounds and analyses of Boolean functions under multiplication or addition.