Multiply with carry generators improved for faster quality random numbers
Scrambled Multiply-with-Carry Pseudorandom Number Generators
Cryptography and SecurityMathematical Software
Summary
Pseudorandom number generators are important for simulations and computations, but some are limited by their internal math structure. The authors show that multiply-with-carry (MWC) generators have structural weaknesses that affect their randomness quality. They propose a way to improve these generators by mixing their outputs with the carry value, leading to stronger randomness. They also suggest specific settings for building fast and reliable MWC generators with larger internal states.
What this means in practice
- •For simulation engineers: Implement high-speed pseudorandom number generators with improved randomness for large-scale simulations requiring 64 to 256 bits of internal state.
- •For cryptocurrency developers: Integrate efficient multiply-with-carry RNGs with better output quality for blockchain applications needing fast and reliable random numbers.
Authors
Sebastiano Vigna
Abstract
Multiply-with-carry (MWC) generators are very fast pseudorandom number generators whose quality depends on the choice of a multiplier, and is usually assessed by applying the spectral test to an associated multiplicative congruential generator. We show that the special form of the modulus imposes structural limitations on the lattice structure of every MWC generator, which the generalized MWC generators of Goresky and Klapper mitigate; in our tests, xoring each output with its carry removes them. Since these limitations make the usual worst-case criterion useless, we rank candidates by a weighted geometric mean of their figures of merit, which does not depend on their normalization, and suggest multipliers for generators with 64 to 256 bits of state. Along the way, we correct some errors in the literature. In the end, we propose MWC192X, a 64-bit generator with 192 bits of state that passes all tests we are aware of, and emits an output in half a nanosecond.